[
https://issues.apache.org/jira/browse/LUCENE-10069?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17445500#comment-17445500
]
ASF subversion and git services commented on LUCENE-10069:
----------------------------------------------------------
Commit 3b914a4d73eea8923f823cbdb869de39213411dd in lucene's branch
refs/heads/hnsw from Julie Tibshirani
[ https://gitbox.apache.org/repos/asf?p=lucene.git;h=3b914a4 ]
LUCENE-10069: Document that kNN queries might not return all results (#434)
Performing a kNN search with very large k may return fewer than k documents.
This is due to the fact that the HNSW graph is not guaranteed to be connected.
This commit documents the behavior as part of a general warning that the results
of a kNN search may be approximate.
> 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
> Time Spent: 20m
> Remaining Estimate: 0h
>
> 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.20.1#820001)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
