[jira] [Comment Edited] (LUCENE-10069) HNSW can miss results with very large k

["Michael Sokolov (Jira)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/LUCENE-10069?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17404690#comment-17404690 ] 

Michael Sokolov edited comment on LUCENE-10069 at 8/25/21, 8:01 PM:
--------------------------------------------------------------------

also, I found it is easy to reproduce this several times by running {TestKnnVectorQuery} with {-Ptests.iters=1000}

 

I truly hate this editor - I can never figure out how to make styled text in it!


was (Author: sokolov):
also, I found it is easy to reproduce this several times by running {{TestKnnVectorQuery }}with -Ptests.iters=1000

> HNSW can miss results with very large k
> ---------------------------------------
>
>                 Key: LUCENE-10069
>                 URL: https://issues.apache.org/jira/browse/LUCENE-10069
>             Project: Lucene - Core
>          Issue Type: Bug
>            Reporter: Julie Tibshirani
>            Priority: Minor
>
> Performing a kNN search with very large k (where k is close to the total number of live docs) can return fewer than k documents. This occurs because searches aren't guaranteed to be able to visit every node in the graph. Specifically, when choosing entry points for the search, we make k random draws _with replacement_, and sometimes end up with fewer than k entry points. These entry points may not provide a connection to all other nodes in the graph.
> This is an unusual case, but I think it'd be nice if we could always return k docs when they are available (or at least document the behavior?) We're currently working on adding graph layers (LUCENE-10054), which will change how entry points are selected. Maybe we can revisit this issue once that work is further along to see if a fix is still needed.
> Here's an example test failure showing the problem. We happen to select {{numDocs=101}} and {{k=100}}.
> {code:java}
> ./gradlew test --tests TestKnnVectorQuery.testRandom -Dtests.seed=3B6CE0E105431E18
> {code}



--
This message was sent by Atlassian Jira
(v8.3.4#803005)

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