Julie Tibshirani created LUCENE-10069:
-----------------------------------------
Summary: 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: Improvement
Reporter: Julie Tibshirani
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: [email protected]
For additional commands, e-mail: [email protected]
