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 2023/11/06 13:05:02 UTC

[PR] Only explore neighbor-of-neighbor if similarity is better [lucene]

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

   I noticed while testing lower dimensionality and quantization, we would explore the HNSW graph way too much. I was stuck figuring out why until I noticed the searcher checks for distance equality (not just if the distance is better) when exploring neighbors-of-neighbors. This seems like a bad heurstic, but to double check I looked at what nmslib does. This pointed me back to this commit: https://github.com/nmslib/nmslib/pull/106
   
   Seems like this performance hitch was discovered awhile ago :). 
   
   This commit adjusts HNSW to only explore the graph layer if the distance is actually better.


-- 
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] Only explore neighbor-of-neighbor if similarity is better [lucene]

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


##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphSearcher.java:
##########
@@ -174,8 +174,7 @@ private int[] findBestEntryPoint(RandomVectorScorer scorer, HnswGraph graph, lon
           }
           float friendSimilarity = scorer.score(friendOrd);
           visitedCount++;
-          if (friendSimilarity > currentScore
-              || (friendSimilarity == currentScore && friendOrd < currentEp)) {
+          if (friendSimilarity > currentScore) {

Review Comment:
   @msokolov I am not 100% sure if we want to do continue exploring if the ordinal is less than the friend ordinal.
   
   I originally made this change to make it more inline with what the typical `results.collect` does, which is a tie breaker over ordinal collected. But, it seems weird to explore the graph in two separate ways. 
   
   I will happily switch this back to tie break on ordinals as this isn't really the bottle neck.



-- 
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] Stop exploring HNSW graph if scores are not getting better. [lucene]

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


##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphSearcher.java:
##########
@@ -174,8 +174,7 @@ private int[] findBestEntryPoint(RandomVectorScorer scorer, HnswGraph graph, lon
           }
           float friendSimilarity = scorer.score(friendOrd);
           visitedCount++;
-          if (friendSimilarity > currentScore
-              || (friendSimilarity == currentScore && friendOrd < currentEp)) {
+          if (friendSimilarity > currentScore) {

Review Comment:
   I see, nothing relies on this tiebreaking I think since we don't apply any ordered iteration over ordinals. +1 to simplify



-- 
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] Stop exploring HNSW graph if scores are not getting better. [lucene]

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

   oh, good catch! I guess equality is unusual, but this should help in some cases. I wonder if it helps with degenerate case where all scores are equal? EG all zero vectors 


-- 
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] Stop exploring HNSW graph if scores are not getting better. [lucene]

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


-- 
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] Stop exploring HNSW graph if scores are not getting better. [lucene]

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

   > I wonder if it helps with degenerate case where all scores are equal? EG all zero vectors (see https://github.com/apache/lucene/issues/11626)
   
   It would help by ending exploration for sure.
   
   In this degenerate case, it is even worse than causing slowness. If there are millions of vectors we could cause an OOME as there are no barriers preventing the candidate list from expanding (we only pop one, but then could add 15 more on each neighbor explored for example).
   
   


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