You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "benwtrent (via GitHub)" <gi...@apache.org> on 2025/03/17 18:22:13 UTC

[PR] Adjust equivalent min similarity HNSW exploration logic [lucene]

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

   It was tempting to just adjust the test data, but this seems like something the searcher should do regardles...
   
   While the previous bug fix addressed the heat-death of the universe runtime of indexing many equal vectors, it added another weird edge case that tests picked up.
   
   We would actually not explore a single valid candidate if it was the one that actually set the minimum score for exploration. While we shouldn't explore ALL the candidates that have the same score as the minimally accepted score, we should explore at least the first one.
   
   This closes: https://github.com/apache/lucene/issues/14327
   
   Its directly related to:
   
    - https://github.com/apache/lucene/pull/14215
    - https://github.com/apache/lucene/pull/14249


-- 
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] Adjust equivalent min similarity HNSW exploration logic [lucene]

Posted by "mayya-sharipova (via GitHub)" <gi...@apache.org>.
mayya-sharipova commented on code in PR #14366:
URL: https://github.com/apache/lucene/pull/14366#discussion_r2005708592


##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphSearcher.java:
##########
@@ -266,11 +266,21 @@ void searchLevel(
     // A bound that holds the minimum similarity to the query vector that a candidate vector must
     // have to be considered.
     float minAcceptedSimilarity = Math.nextUp(results.minCompetitiveSimilarity());
+    // We should allow exploring equivalent minAcceptedSimilarity values at least once
+    boolean shouldExploreMinSim = true;
     while (candidates.size() > 0 && results.earlyTerminated() == false) {
       // get the best candidate (closest or best scoring)
       float topCandidateSimilarity = candidates.topScore();
       if (topCandidateSimilarity < minAcceptedSimilarity) {
-        break;
+        // if the similarity is equivalent to the minAcceptedSimilarity, we should explore one

Review Comment:
   nit: format the comment a little better (auto format seems to break it strangely)



-- 
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] Adjust equivalent min similarity HNSW exploration logic [lucene]

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


-- 
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] Adjust equivalent min similarity HNSW exploration logic [lucene]

Posted by "mayya-sharipova (via GitHub)" <gi...@apache.org>.
mayya-sharipova commented on code in PR #14366:
URL: https://github.com/apache/lucene/pull/14366#discussion_r2005709557


##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphSearcher.java:
##########
@@ -266,11 +266,21 @@ void searchLevel(
     // A bound that holds the minimum similarity to the query vector that a candidate vector must
     // have to be considered.
     float minAcceptedSimilarity = Math.nextUp(results.minCompetitiveSimilarity());
+    // We should allow exploring equivalent minAcceptedSimilarity values at least once
+    boolean shouldExploreMinSim = true;
     while (candidates.size() > 0 && results.earlyTerminated() == false) {
       // get the best candidate (closest or best scoring)
       float topCandidateSimilarity = candidates.topScore();
       if (topCandidateSimilarity < minAcceptedSimilarity) {
-        break;
+        // if the similarity is equivalent to the minAcceptedSimilarity, we should explore one
+        // candidate
+        // however, running into many duplicates can be expensive, so we should stop exploring if
+        // equivalent minimum scores are found
+        if (shouldExploreMinSim && Math.nextUp(candidates.topScore()) == minAcceptedSimilarity) {

Review Comment:
   if (shouldExploreMinSim && Math.nextUp(candidates.topScore()) == minAcceptedSimilarity) => 
   if (shouldExploreMinSim && Math.nextUp(topCandidateSimilarity) == minAcceptedSimilarity)



-- 
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