You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "harenlin (via GitHub)" <gi...@apache.org> on 2024/06/07 18:45:27 UTC

[PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

harenlin opened a new pull request, #13470:
URL: https://github.com/apache/lucene/pull/13470

   ### Description
   Hello the community,
   
   Hank and I just follow the [discussion thread](https://lists.apache.org/thread/j2q4b8dfhoh1x15vo1myt357y5vtjl7z) to implement the RRF function that can be used. By the way, we know that the RRF issue is under debate in solr ([FYR](https://github.com/apache/solr/pull/2489)); however, we think this new feature could still be a good one.
   
   <!--
   If this is your first contribution to Lucene, please make sure you have reviewed the contribution guide.
   https://github.com/apache/lucene/blob/main/CONTRIBUTING.md
   -->
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "hack4chang (via GitHub)" <gi...@apache.org>.
hack4chang commented on code in PR #13470:
URL: https://github.com/apache/lucene/pull/13470#discussion_r1632101267


##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,38 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  /** Reciprocal Rank Fusion method. */
+  public static TopDocs rrf(int TopN, int k, TopDocs[] hits) {

Review Comment:
   Oops, my bad.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "hack4chang (via GitHub)" <gi...@apache.org>.
hack4chang commented on code in PR #13470:
URL: https://github.com/apache/lucene/pull/13470#discussion_r1632101139


##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,38 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  /** Reciprocal Rank Fusion method. */

Review Comment:
   Do we have to check if the k value is greater than or equal to 1 in the code? And maybe mention it in the javadocs?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "hack4chang (via GitHub)" <gi...@apache.org>.
hack4chang commented on code in PR #13470:
URL: https://github.com/apache/lucene/pull/13470#discussion_r1632111769


##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,38 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  /** Reciprocal Rank Fusion method. */
+  public static TopDocs rrf(int TopN, int k, TopDocs[] hits) {
+    Map<Integer, Float> rrfScore = new HashMap<>();
+    long minHits = Long.MAX_VALUE;
+    for (TopDocs topDoc : hits) {
+      minHits = Math.min(minHits, topDoc.totalHits.value);
+      Map<Integer, Float> scoreMap = new HashMap<>();
+      for (ScoreDoc scoreDoc : topDoc.scoreDocs) {
+        scoreMap.put(scoreDoc.doc, scoreDoc.score);
+      }
+
+      List<Map.Entry<Integer, Float>> scoreList = new ArrayList<>(scoreMap.entrySet());
+      scoreList.sort(Map.Entry.comparingByValue());
+
+      int rank = 1;
+      for (ScoreDoc scoreDoc : topDoc.scoreDocs) {
+        rrfScore.put(scoreDoc.doc, rrfScore.getOrDefault(scoreDoc.doc, 0.0f) + 1.0f / (rank + k));
+        rank++;
+      }
+    }
+
+    List<Map.Entry<Integer, Float>> rrfScoreRank = new ArrayList<>(rrfScore.entrySet());
+    rrfScoreRank.sort(
+        Map.Entry.<Integer, Float>comparingByValue().reversed()); // Sort in descending order
+
+    ScoreDoc[] rrfScoreDocs = new ScoreDoc[Math.min(TopN, rrfScoreRank.size())];
+    for (int i = 0; i < rrfScoreDocs.length; i++) {
+      rrfScoreDocs[i] = new ScoreDoc(rrfScoreRank.get(i).getKey(), rrfScoreRank.get(i).getValue());

Review Comment:
   So this was also a tricky part for us. For my understanding, the RRF would combine search result based on the different ranks of a documents in different results. We supposed to combine the ranks for all individual doucments, but a document come from different shards should be treated as different documents? 



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "javanna (via GitHub)" <gi...@apache.org>.
javanna commented on code in PR #13470:
URL: https://github.com/apache/lucene/pull/13470#discussion_r1973180965


##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,89 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  private record ShardIndexAndDoc(int shardIndex, int doc) {}
+
+  /**
+   * Reciprocal Rank Fusion method.
+   *
+   * <p>This method combines different search results into a single ranked list by combining their
+   * ranks. This is especially well suited when combining hits computed via different methods, whose
+   * score distributions are hardly comparable.
+   *
+   * @param topN the top N results to be returned
+   * @param k a constant determines how much influence documents in individual rankings have on the
+   *     final result. A higher value gives lower rank documents more influence. k should be greater
+   *     than or equal to 1.
+   * @param hits a list of TopDocs to apply RRF on
+   * @return a TopDocs contains the top N ranked results.
+   */
+  public static TopDocs rrf(int topN, int k, TopDocs[] hits) {
+    if (topN < 1) {
+      throw new IllegalArgumentException("topN must be >= 1, got " + topN);
+    }
+    if (k < 1) {
+      throw new IllegalArgumentException("k must be >= 1, got " + k);
+    }
+
+    boolean shardIndexSet = false;
+    outer:
+    for (TopDocs topDocs : hits) {
+      for (ScoreDoc scoreDoc : topDocs.scoreDocs) {
+        shardIndexSet = scoreDoc.shardIndex != -1;
+        break outer;

Review Comment:
   yes, thank you!



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "alessandrobenedetti (via GitHub)" <gi...@apache.org>.
alessandrobenedetti commented on PR #13470:
URL: https://github.com/apache/lucene/pull/13470#issuecomment-2156437678

   I'm not sure 'rrf' should be a direct method in topDocs:
   Reciprocal Rank Fusion is just one way of combining result sets, if in the future we want to add other algorithms having 'rrf' there may encourage to just add and add to topDocs.
   What about having a "combine" method there, potentially taking in input the combining strategy?
   Then abstract the combining strategy as an interface/abstract class and implement Reciprocal Rank Fusion as the first available strategy? That should ease the process of adding more strategies and prevent TopDocs to become too dirty in the future.
   
   N.B. I am generally in favour of "You are Not Gonna Need It' approach, but in Lucene's instance we have many contributors and future contributors that may get involved, and doing this abstraction work  when and if "a second strategy" gets implemented may not happen


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #13470:
URL: https://github.com/apache/lucene/pull/13470#discussion_r1632257926


##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,38 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  /** Reciprocal Rank Fusion method. */
+  public static TopDocs rrf(int TopN, int k, TopDocs[] hits) {
+    Map<Integer, Float> rrfScore = new HashMap<>();
+    long minHits = Long.MAX_VALUE;
+    for (TopDocs topDoc : hits) {
+      minHits = Math.min(minHits, topDoc.totalHits.value);
+      Map<Integer, Float> scoreMap = new HashMap<>();
+      for (ScoreDoc scoreDoc : topDoc.scoreDocs) {
+        scoreMap.put(scoreDoc.doc, scoreDoc.score);
+      }
+
+      List<Map.Entry<Integer, Float>> scoreList = new ArrayList<>(scoreMap.entrySet());
+      scoreList.sort(Map.Entry.comparingByValue());
+
+      int rank = 1;
+      for (ScoreDoc scoreDoc : topDoc.scoreDocs) {
+        rrfScore.put(scoreDoc.doc, rrfScore.getOrDefault(scoreDoc.doc, 0.0f) + 1.0f / (rank + k));
+        rank++;
+      }
+    }
+
+    List<Map.Entry<Integer, Float>> rrfScoreRank = new ArrayList<>(rrfScore.entrySet());
+    rrfScoreRank.sort(
+        Map.Entry.<Integer, Float>comparingByValue().reversed()); // Sort in descending order
+
+    ScoreDoc[] rrfScoreDocs = new ScoreDoc[Math.min(TopN, rrfScoreRank.size())];
+    for (int i = 0; i < rrfScoreDocs.length; i++) {
+      rrfScoreDocs[i] = new ScoreDoc(rrfScoreRank.get(i).getKey(), rrfScoreRank.get(i).getValue());

Review Comment:
   This is correct. When working with shards, hits should first be combined on a per-query basis using TopDocs#merge, which will set the shardIndex field. And then global top hits can be merged across queries with RRF.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "javanna (via GitHub)" <gi...@apache.org>.
javanna commented on PR #13470:
URL: https://github.com/apache/lucene/pull/13470#issuecomment-2677773959

   This looks good to me. Perhaps we could mark the new static method experimental, especially if we think we are going to want to support more ways of combining topdocs soon enough. I don't have a strong opinion though, it would also be ok to introduce a more flexible way to do rrf while keeping this one around until the next major.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "javanna (via GitHub)" <gi...@apache.org>.
javanna commented on code in PR #13470:
URL: https://github.com/apache/lucene/pull/13470#discussion_r1967234360


##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,89 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  private record ShardIndexAndDoc(int shardIndex, int doc) {}
+
+  /**
+   * Reciprocal Rank Fusion method.
+   *
+   * <p>This method combines different search results into a single ranked list by combining their
+   * ranks. This is especially well suited when combining hits computed via different methods, whose
+   * score distributions are hardly comparable.
+   *
+   * @param topN the top N results to be returned
+   * @param k a constant determines how much influence documents in individual rankings have on the
+   *     final result. A higher value gives lower rank documents more influence. k should be greater
+   *     than or equal to 1.
+   * @param hits a list of TopDocs to apply RRF on
+   * @return a TopDocs contains the top N ranked results.
+   */
+  public static TopDocs rrf(int topN, int k, TopDocs[] hits) {
+    if (topN < 1) {
+      throw new IllegalArgumentException("topN must be >= 1, got " + topN);
+    }
+    if (k < 1) {
+      throw new IllegalArgumentException("k must be >= 1, got " + k);
+    }
+
+    boolean shardIndexSet = false;
+    outer:
+    for (TopDocs topDocs : hits) {
+      for (ScoreDoc scoreDoc : topDocs.scoreDocs) {
+        shardIndexSet = scoreDoc.shardIndex != -1;
+        break outer;

Review Comment:
   Is the purpose here to only check the first scoreDoc of every TopDocs instance provided in the array? Should we try and rewrite this to be more readable and not use goto ?



##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,89 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  private record ShardIndexAndDoc(int shardIndex, int doc) {}
+
+  /**
+   * Reciprocal Rank Fusion method.
+   *
+   * <p>This method combines different search results into a single ranked list by combining their
+   * ranks. This is especially well suited when combining hits computed via different methods, whose
+   * score distributions are hardly comparable.
+   *
+   * @param topN the top N results to be returned
+   * @param k a constant determines how much influence documents in individual rankings have on the
+   *     final result. A higher value gives lower rank documents more influence. k should be greater
+   *     than or equal to 1.
+   * @param hits a list of TopDocs to apply RRF on
+   * @return a TopDocs contains the top N ranked results.
+   */
+  public static TopDocs rrf(int topN, int k, TopDocs[] hits) {
+    if (topN < 1) {
+      throw new IllegalArgumentException("topN must be >= 1, got " + topN);
+    }
+    if (k < 1) {
+      throw new IllegalArgumentException("k must be >= 1, got " + k);
+    }
+
+    boolean shardIndexSet = false;
+    outer:
+    for (TopDocs topDocs : hits) {
+      for (ScoreDoc scoreDoc : topDocs.scoreDocs) {
+        shardIndexSet = scoreDoc.shardIndex != -1;
+        break outer;
+      }
+    }
+    for (TopDocs topDocs : hits) {

Review Comment:
   would it make sense to check shardIndex while we loop later, rather than looping multiple times through all of the docs?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #13470:
URL: https://github.com/apache/lucene/pull/13470#issuecomment-2689114469

   > I have a bias for the latter, as I was planning on improving the docs of the oal.search package as a follow-up to provide guidance wrt how to do hybrid search by linking to this RRF helper.
   
   I opened #14310.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #13470:
URL: https://github.com/apache/lucene/pull/13470#discussion_r1972392963


##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,89 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  private record ShardIndexAndDoc(int shardIndex, int doc) {}
+
+  /**
+   * Reciprocal Rank Fusion method.
+   *
+   * <p>This method combines different search results into a single ranked list by combining their
+   * ranks. This is especially well suited when combining hits computed via different methods, whose
+   * score distributions are hardly comparable.
+   *
+   * @param topN the top N results to be returned
+   * @param k a constant determines how much influence documents in individual rankings have on the
+   *     final result. A higher value gives lower rank documents more influence. k should be greater
+   *     than or equal to 1.
+   * @param hits a list of TopDocs to apply RRF on
+   * @return a TopDocs contains the top N ranked results.
+   */
+  public static TopDocs rrf(int topN, int k, TopDocs[] hits) {
+    if (topN < 1) {
+      throw new IllegalArgumentException("topN must be >= 1, got " + topN);
+    }
+    if (k < 1) {
+      throw new IllegalArgumentException("k must be >= 1, got " + k);
+    }
+
+    boolean shardIndexSet = false;
+    outer:
+    for (TopDocs topDocs : hits) {
+      for (ScoreDoc scoreDoc : topDocs.scoreDocs) {
+        shardIndexSet = scoreDoc.shardIndex != -1;
+        break outer;
+      }
+    }
+    for (TopDocs topDocs : hits) {

Review Comment:
   I don't feel too strongly about it, but I found it to hurt readability by polluting the RRF logic with shardIndex validation.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "hack4chang (via GitHub)" <gi...@apache.org>.
hack4chang commented on code in PR #13470:
URL: https://github.com/apache/lucene/pull/13470#discussion_r1632104552


##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,38 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  /** Reciprocal Rank Fusion method. */
+  public static TopDocs rrf(int TopN, int k, TopDocs[] hits) {
+    Map<Integer, Float> rrfScore = new HashMap<>();
+    long minHits = Long.MAX_VALUE;
+    for (TopDocs topDoc : hits) {
+      minHits = Math.min(minHits, topDoc.totalHits.value);

Review Comment:
   The totalHits was a tricky part that we didn't know what value to assign to. IIUC, The totalHits means all the matched Document in a query, and we couldn't really calculate the union of the totalHits for all the TopDocs. So for this min totalHits, I just wanted to assign a min totalHits temporarily, to match the totalHits relation "greater than or equal to". And I want to ask for your opinion on this.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #13470:
URL: https://github.com/apache/lucene/pull/13470#discussion_r1972397524


##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,89 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  private record ShardIndexAndDoc(int shardIndex, int doc) {}
+
+  /**
+   * Reciprocal Rank Fusion method.
+   *
+   * <p>This method combines different search results into a single ranked list by combining their
+   * ranks. This is especially well suited when combining hits computed via different methods, whose
+   * score distributions are hardly comparable.
+   *
+   * @param topN the top N results to be returned
+   * @param k a constant determines how much influence documents in individual rankings have on the
+   *     final result. A higher value gives lower rank documents more influence. k should be greater
+   *     than or equal to 1.
+   * @param hits a list of TopDocs to apply RRF on
+   * @return a TopDocs contains the top N ranked results.
+   */
+  public static TopDocs rrf(int topN, int k, TopDocs[] hits) {
+    if (topN < 1) {
+      throw new IllegalArgumentException("topN must be >= 1, got " + topN);
+    }
+    if (k < 1) {
+      throw new IllegalArgumentException("k must be >= 1, got " + k);
+    }
+
+    boolean shardIndexSet = false;
+    outer:
+    for (TopDocs topDocs : hits) {
+      for (ScoreDoc scoreDoc : topDocs.scoreDocs) {
+        shardIndexSet = scoreDoc.shardIndex != -1;
+        break outer;

Review Comment:
   Does it look better now?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #13470:
URL: https://github.com/apache/lucene/pull/13470#issuecomment-2674572334

   I plan on merging this PR soon if there are no objections.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "harenlin (via GitHub)" <gi...@apache.org>.
harenlin commented on code in PR #13470:
URL: https://github.com/apache/lucene/pull/13470#discussion_r1632391085


##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,38 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  /** Reciprocal Rank Fusion method. */
+  public static TopDocs rrf(int TopN, int k, TopDocs[] hits) {
+    Map<Integer, Float> rrfScore = new HashMap<>();
+    long minHits = Long.MAX_VALUE;
+    for (TopDocs topDoc : hits) {
+      minHits = Math.min(minHits, topDoc.totalHits.value);
+      Map<Integer, Float> scoreMap = new HashMap<>();
+      for (ScoreDoc scoreDoc : topDoc.scoreDocs) {
+        scoreMap.put(scoreDoc.doc, scoreDoc.score);
+      }
+
+      List<Map.Entry<Integer, Float>> scoreList = new ArrayList<>(scoreMap.entrySet());
+      scoreList.sort(Map.Entry.comparingByValue());

Review Comment:
   Oops! My bad. I think we got something wrong right here. The for loop traversal ```for (ScoreDoc scoreDoc : topDoc.scoreDocs)``` is wrong, we should actually traverse the sorted results, i.e., scoreList, to add the ranking result to ```rrfScore```. 
   
   ```
   int rank = 1;
   for (Map.Entry<Integer, Float> entry : scoreList.entrySet()) {
       rrfScore.put(entry.getKey(), 
                    rrfScore.getOrDefault(entry.getKey(), 0.0f) + 1 / (rank + k));
       rank++;
   }
   ```
   
   P.S. For this part, however, I think we should determine the implementation of combining ```ScoreDoc.doc``` and ```ScoreDoc.shardIndex``` together first.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "harenlin (via GitHub)" <gi...@apache.org>.
harenlin commented on code in PR #13470:
URL: https://github.com/apache/lucene/pull/13470#discussion_r1632391085


##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,38 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  /** Reciprocal Rank Fusion method. */
+  public static TopDocs rrf(int TopN, int k, TopDocs[] hits) {
+    Map<Integer, Float> rrfScore = new HashMap<>();
+    long minHits = Long.MAX_VALUE;
+    for (TopDocs topDoc : hits) {
+      minHits = Math.min(minHits, topDoc.totalHits.value);
+      Map<Integer, Float> scoreMap = new HashMap<>();
+      for (ScoreDoc scoreDoc : topDoc.scoreDocs) {
+        scoreMap.put(scoreDoc.doc, scoreDoc.score);
+      }
+
+      List<Map.Entry<Integer, Float>> scoreList = new ArrayList<>(scoreMap.entrySet());
+      scoreList.sort(Map.Entry.comparingByValue());

Review Comment:
   Oops! My bad. I think we got something wrong right here. The for loop traversal ```for (ScoreDoc scoreDoc : topDoc.scoreDocs)``` is wrong, we should actually traverse the sorted results, i.e., scoreList, to add the ranking result to ```rrfScore```. 
   
   P.S. For this part, however, I think we should determine the implementation of combining ```ScoreDoc.doc``` and ```ScoreDoc.shardIndex``` together first.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #13470:
URL: https://github.com/apache/lucene/pull/13470#issuecomment-2659645405

   @harenlin I took some freedom to apply my feedback and push it to your branch. Would you like to take a look and check if it makes sense?


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #13470:
URL: https://github.com/apache/lucene/pull/13470#discussion_r1632257416


##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,38 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  /** Reciprocal Rank Fusion method. */
+  public static TopDocs rrf(int TopN, int k, TopDocs[] hits) {
+    Map<Integer, Float> rrfScore = new HashMap<>();
+    long minHits = Long.MAX_VALUE;
+    for (TopDocs topDoc : hits) {
+      minHits = Math.min(minHits, topDoc.totalHits.value);

Review Comment:
   I agree with using GREATER_THAN_OR_EQUAL_TO all the time, but I would still take the max, because a document is a match of it is a match to either query. For instance, imagine combining top hits from two queries where one query didn't match any docs, the total hit count should be the hit count of the other query, not zero?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "harenlin (via GitHub)" <gi...@apache.org>.
harenlin commented on code in PR #13470:
URL: https://github.com/apache/lucene/pull/13470#discussion_r1632394832


##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,38 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  /** Reciprocal Rank Fusion method. */
+  public static TopDocs rrf(int TopN, int k, TopDocs[] hits) {
+    Map<Integer, Float> rrfScore = new HashMap<>();
+    long minHits = Long.MAX_VALUE;
+    for (TopDocs topDoc : hits) {
+      minHits = Math.min(minHits, topDoc.totalHits.value);
+      Map<Integer, Float> scoreMap = new HashMap<>();
+      for (ScoreDoc scoreDoc : topDoc.scoreDocs) {
+        scoreMap.put(scoreDoc.doc, scoreDoc.score);
+      }
+
+      List<Map.Entry<Integer, Float>> scoreList = new ArrayList<>(scoreMap.entrySet());
+      scoreList.sort(Map.Entry.comparingByValue());
+
+      int rank = 1;
+      for (ScoreDoc scoreDoc : topDoc.scoreDocs) {
+        rrfScore.put(scoreDoc.doc, rrfScore.getOrDefault(scoreDoc.doc, 0.0f) + 1.0f / (rank + k));

Review Comment:
   Sounds good! I don't know ```Map#compute``` before tho. It should be like below: 
   ```
   int rank = 1;
   for (Map.Entry<Integer, Float> entry : scoreList.entrySet()) {
       rrfScore.compute(entry.getKey(), (key, value) -> 
           (value == null ? 0.0f : value) + 1 / (float)(rank + k)
       );
       rank++;
   }
   ```



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "hack4chang (via GitHub)" <gi...@apache.org>.
hack4chang commented on code in PR #13470:
URL: https://github.com/apache/lucene/pull/13470#discussion_r1632104552


##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,38 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  /** Reciprocal Rank Fusion method. */
+  public static TopDocs rrf(int TopN, int k, TopDocs[] hits) {
+    Map<Integer, Float> rrfScore = new HashMap<>();
+    long minHits = Long.MAX_VALUE;
+    for (TopDocs topDoc : hits) {
+      minHits = Math.min(minHits, topDoc.totalHits.value);

Review Comment:
   The totalHits was a tricky part that we didn't know what value to assign to. IIUC, The totalHits means all the matched Document in a query, and we couldn't really calculate the union of the totalHits for all the TopDocs. So for this min totalHits, I just want to assign a min totalHits for now, to match the totalHits relation "greater than or equal to". And I want to ask for your opinion on this.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #13470:
URL: https://github.com/apache/lucene/pull/13470#discussion_r1631987192


##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,38 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  /** Reciprocal Rank Fusion method. */
+  public static TopDocs rrf(int TopN, int k, TopDocs[] hits) {
+    Map<Integer, Float> rrfScore = new HashMap<>();
+    long minHits = Long.MAX_VALUE;
+    for (TopDocs topDoc : hits) {
+      minHits = Math.min(minHits, topDoc.totalHits.value);
+      Map<Integer, Float> scoreMap = new HashMap<>();
+      for (ScoreDoc scoreDoc : topDoc.scoreDocs) {
+        scoreMap.put(scoreDoc.doc, scoreDoc.score);
+      }
+
+      List<Map.Entry<Integer, Float>> scoreList = new ArrayList<>(scoreMap.entrySet());
+      scoreList.sort(Map.Entry.comparingByValue());

Review Comment:
   We don't seem to be using these `scoreMap` and `scoreList` anywhere?



##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,38 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  /** Reciprocal Rank Fusion method. */
+  public static TopDocs rrf(int TopN, int k, TopDocs[] hits) {
+    Map<Integer, Float> rrfScore = new HashMap<>();
+    long minHits = Long.MAX_VALUE;
+    for (TopDocs topDoc : hits) {
+      minHits = Math.min(minHits, topDoc.totalHits.value);
+      Map<Integer, Float> scoreMap = new HashMap<>();
+      for (ScoreDoc scoreDoc : topDoc.scoreDocs) {
+        scoreMap.put(scoreDoc.doc, scoreDoc.score);
+      }
+
+      List<Map.Entry<Integer, Float>> scoreList = new ArrayList<>(scoreMap.entrySet());
+      scoreList.sort(Map.Entry.comparingByValue());
+
+      int rank = 1;
+      for (ScoreDoc scoreDoc : topDoc.scoreDocs) {
+        rrfScore.put(scoreDoc.doc, rrfScore.getOrDefault(scoreDoc.doc, 0.0f) + 1.0f / (rank + k));
+        rank++;
+      }
+    }
+
+    List<Map.Entry<Integer, Float>> rrfScoreRank = new ArrayList<>(rrfScore.entrySet());
+    rrfScoreRank.sort(
+        Map.Entry.<Integer, Float>comparingByValue().reversed()); // Sort in descending order
+
+    ScoreDoc[] rrfScoreDocs = new ScoreDoc[Math.min(TopN, rrfScoreRank.size())];
+    for (int i = 0; i < rrfScoreDocs.length; i++) {
+      rrfScoreDocs[i] = new ScoreDoc(rrfScoreRank.get(i).getKey(), rrfScoreRank.get(i).getValue());

Review Comment:
   Nit: we should preserve the original `shardIndex` that is configured on the `ScoreDoc` object that identifies the shard that it is coming from.



##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,38 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  /** Reciprocal Rank Fusion method. */

Review Comment:
   Users could use more details in these javadocs, e.g. what are `k` and `topN`?



##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,38 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  /** Reciprocal Rank Fusion method. */
+  public static TopDocs rrf(int TopN, int k, TopDocs[] hits) {
+    Map<Integer, Float> rrfScore = new HashMap<>();
+    long minHits = Long.MAX_VALUE;
+    for (TopDocs topDoc : hits) {
+      minHits = Math.min(minHits, topDoc.totalHits.value);

Review Comment:
   I wonder if it should be a `max` rather than a `min`? Presumably, hits from either top hits are considered as hits globally, and we are just using RRF to boost hits that are ranked high in multiple top hits?



##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,38 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  /** Reciprocal Rank Fusion method. */
+  public static TopDocs rrf(int TopN, int k, TopDocs[] hits) {
+    Map<Integer, Float> rrfScore = new HashMap<>();

Review Comment:
   Note that we should identify documents not only by their doc ID, but by the combination of `ScoreDoc.shardIndex` and `ScoreDoc.doc`, as there could be multiple documents that have the same doc ID but come from different shards.



##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,38 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  /** Reciprocal Rank Fusion method. */
+  public static TopDocs rrf(int TopN, int k, TopDocs[] hits) {

Review Comment:
   nit: function arguments should use lower camel case
   
   ```suggestion
     public static TopDocs rrf(int topN, int k, TopDocs[] hits) {
   ```
   
   



##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,38 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  /** Reciprocal Rank Fusion method. */
+  public static TopDocs rrf(int TopN, int k, TopDocs[] hits) {
+    Map<Integer, Float> rrfScore = new HashMap<>();
+    long minHits = Long.MAX_VALUE;
+    for (TopDocs topDoc : hits) {
+      minHits = Math.min(minHits, topDoc.totalHits.value);
+      Map<Integer, Float> scoreMap = new HashMap<>();
+      for (ScoreDoc scoreDoc : topDoc.scoreDocs) {
+        scoreMap.put(scoreDoc.doc, scoreDoc.score);
+      }
+
+      List<Map.Entry<Integer, Float>> scoreList = new ArrayList<>(scoreMap.entrySet());
+      scoreList.sort(Map.Entry.comparingByValue());
+
+      int rank = 1;
+      for (ScoreDoc scoreDoc : topDoc.scoreDocs) {
+        rrfScore.put(scoreDoc.doc, rrfScore.getOrDefault(scoreDoc.doc, 0.0f) + 1.0f / (rank + k));

Review Comment:
   Use `Map#compute` instead of `getOrDefault` + `put`?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #13470:
URL: https://github.com/apache/lucene/pull/13470#issuecomment-2677780646

   Thanks for taking a look. I have a bias for the latter, as I was planning on improving the docs of the oal.search package as a follow-up to provide guidance wrt how to do hybrid search by linking to this RRF helper.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz merged PR #13470:
URL: https://github.com/apache/lucene/pull/13470


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #13470:
URL: https://github.com/apache/lucene/pull/13470#issuecomment-2156511314

   I'm not worried about this. If we feel like we should expose it differently in the future, we'll do it, deprecate this function, and remove it in Lucene 11.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #13470:
URL: https://github.com/apache/lucene/pull/13470#discussion_r1632256442


##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,38 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  /** Reciprocal Rank Fusion method. */

Review Comment:
   +1 to validating parameters



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "hack4chang (via GitHub)" <gi...@apache.org>.
hack4chang commented on code in PR #13470:
URL: https://github.com/apache/lucene/pull/13470#discussion_r1632381076


##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,38 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  /** Reciprocal Rank Fusion method. */
+  public static TopDocs rrf(int TopN, int k, TopDocs[] hits) {
+    Map<Integer, Float> rrfScore = new HashMap<>();
+    long minHits = Long.MAX_VALUE;
+    for (TopDocs topDoc : hits) {
+      minHits = Math.min(minHits, topDoc.totalHits.value);

Review Comment:
   Make sense to me, thank you for the detailed explanation!!



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "hack4chang (via GitHub)" <gi...@apache.org>.
hack4chang commented on code in PR #13470:
URL: https://github.com/apache/lucene/pull/13470#discussion_r1632393474


##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,38 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  /** Reciprocal Rank Fusion method. */
+  public static TopDocs rrf(int TopN, int k, TopDocs[] hits) {
+    Map<Integer, Float> rrfScore = new HashMap<>();
+    long minHits = Long.MAX_VALUE;
+    for (TopDocs topDoc : hits) {
+      minHits = Math.min(minHits, topDoc.totalHits.value);
+      Map<Integer, Float> scoreMap = new HashMap<>();
+      for (ScoreDoc scoreDoc : topDoc.scoreDocs) {
+        scoreMap.put(scoreDoc.doc, scoreDoc.score);
+      }
+
+      List<Map.Entry<Integer, Float>> scoreList = new ArrayList<>(scoreMap.entrySet());
+      scoreList.sort(Map.Entry.comparingByValue());
+
+      int rank = 1;
+      for (ScoreDoc scoreDoc : topDoc.scoreDocs) {
+        rrfScore.put(scoreDoc.doc, rrfScore.getOrDefault(scoreDoc.doc, 0.0f) + 1.0f / (rank + k));
+        rank++;
+      }
+    }
+
+    List<Map.Entry<Integer, Float>> rrfScoreRank = new ArrayList<>(rrfScore.entrySet());
+    rrfScoreRank.sort(
+        Map.Entry.<Integer, Float>comparingByValue().reversed()); // Sort in descending order
+
+    ScoreDoc[] rrfScoreDocs = new ScoreDoc[Math.min(TopN, rrfScoreRank.size())];
+    for (int i = 0; i < rrfScoreDocs.length; i++) {
+      rrfScoreDocs[i] = new ScoreDoc(rrfScoreRank.get(i).getKey(), rrfScoreRank.get(i).getValue());

Review Comment:
   If we do the rrf by setting the unique key as docid and shardIndex, what would be the difference between TopDocs#rrf and TopDocs#merge? I think giving an example could express better. Suppose that we have two Shards, and we want to retrieve top 3 results from each shards and do rrf on top of them. There's three documents A, B and C. In Shard1, the top 3 is A -> B -> C. In Shard2, it's B -> C -> A. The original rrf method would calculate the rank by aggregating the docid, assume the constant k is 1. Top 3 results would be B ```(1/(k+2) + 1/(k+1))``` - A ```(1/(k+1) + 1/(k+3))``` - C ```(1/(k+3) + 1/(k+2))```.
   If we are going to consider the shardIndex as a unique key as well, how should the rrf rank to be presented.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Reciprocal Rank Fusion (RRF) in TopDocs [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #13470:
URL: https://github.com/apache/lucene/pull/13470#discussion_r1642654043


##########
lucene/core/src/java/org/apache/lucene/search/TopDocs.java:
##########
@@ -350,4 +354,38 @@ private static TopDocs mergeAux(
       return new TopFieldDocs(totalHits, hits, sort.getSort());
     }
   }
+
+  /** Reciprocal Rank Fusion method. */
+  public static TopDocs rrf(int TopN, int k, TopDocs[] hits) {
+    Map<Integer, Float> rrfScore = new HashMap<>();
+    long minHits = Long.MAX_VALUE;
+    for (TopDocs topDoc : hits) {
+      minHits = Math.min(minHits, topDoc.totalHits.value);
+      Map<Integer, Float> scoreMap = new HashMap<>();
+      for (ScoreDoc scoreDoc : topDoc.scoreDocs) {
+        scoreMap.put(scoreDoc.doc, scoreDoc.score);
+      }
+
+      List<Map.Entry<Integer, Float>> scoreList = new ArrayList<>(scoreMap.entrySet());
+      scoreList.sort(Map.Entry.comparingByValue());
+
+      int rank = 1;
+      for (ScoreDoc scoreDoc : topDoc.scoreDocs) {
+        rrfScore.put(scoreDoc.doc, rrfScore.getOrDefault(scoreDoc.doc, 0.0f) + 1.0f / (rank + k));
+        rank++;
+      }
+    }
+
+    List<Map.Entry<Integer, Float>> rrfScoreRank = new ArrayList<>(rrfScore.entrySet());
+    rrfScoreRank.sort(
+        Map.Entry.<Integer, Float>comparingByValue().reversed()); // Sort in descending order
+
+    ScoreDoc[] rrfScoreDocs = new ScoreDoc[Math.min(TopN, rrfScoreRank.size())];
+    for (int i = 0; i < rrfScoreDocs.length; i++) {
+      rrfScoreDocs[i] = new ScoreDoc(rrfScoreRank.get(i).getKey(), rrfScoreRank.get(i).getValue());

Review Comment:
   When working with shards, shards managed non-overlapping subsets of the data, so you could not have documents A, B and C in both shards.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org