[jira] [Commented] (LUCENE-10040) Handle deletions in nearest vector search

["Adrien Grand (Jira)" <ji...@apache.org>]

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

Adrien Grand commented on LUCENE-10040:
---------------------------------------

bq. Performance can be unpredictable. If deletions are random, it shouldn't have a huge effect. But in the worst case, a segment could have 50% deleted docs, and they all happen to be near the query vector. HNSW would need to traverse through around half the entire graph to collect neighbors.

FWIW this is a general problem with Lucene. For instance if you run a term query, we'll use impacts to know which blocks may contain competitive documents, but we could hit a worst-case scenario where the documents that make the block competitive are deleted, and all the non-deleted documents of the block are not competitive.

> Handle deletions in nearest vector search
> -----------------------------------------
>
>                 Key: LUCENE-10040
>                 URL: https://issues.apache.org/jira/browse/LUCENE-10040
>             Project: Lucene - Core
>          Issue Type: Improvement
>            Reporter: Julie Tibshirani
>            Priority: Major
>
> Currently nearest vector search doesn't account for deleted documents. Even if a document is not in {{LeafReader#getLiveDocs}}, it could still be returned from {{LeafReader#searchNearestVectors}}. This seems like it'd be surprising + difficult for users, since other search APIs account for deleted docs. We've discussed extending {{searchNearestVectors}} to take a parameter like {{Bits liveDocs}}. This issue discusses options around adding support.
> One approach is to just filter out deleted docs after running the KNN search. This behavior seems hard to work with as a user: fewer than {{k}} docs might come back from your KNN search!
> Alternatively, {{LeafReader#searchNearestVectors}} could always return the {{k}} nearest undeleted docs. To implement this, HNSW could omit deleted docs while assembling its candidate list. It would traverse further into the graph, visiting more nodes to ensure it gathers the required candidates. (Note deleted docs would still be visited/ traversed). The [hnswlib library|https://github.com/nmslib/hnswlib] contains an implementation like this, where you can mark documents as deleted and they're skipped during search.
> This approach seems reasonable to me, but there are some challenges:
>  * Performance can be unpredictable. If deletions are random, it shouldn't have a huge effect. But in the worst case, a segment could have 50% deleted docs, and they all happen to be near the query vector. HNSW would need to traverse through around half the entire graph to collect neighbors.
>  * As far as I know, there hasn't been academic research or any testing into how well this performs in terms of recall. I have a vague intuition it could be harder to achieve high recall as the algorithm traverses areas further from the "natural" entry points. The HNSW paper doesn't mention deletions/ filtering, and I haven't seen community benchmarks around it.
> Background links:
>  * Thoughts on deletions from the author of the HNSW paper: [https://github.com/nmslib/hnswlib/issues/4#issuecomment-378739892]
>  * Blog from Vespa team which mentions combining KNN and search filters (very similar to applying deleted docs): [https://blog.vespa.ai/approximate-nearest-neighbor-search-in-vespa-part-1/]. The "Exact vs Approximate" section shows good performance even when a large percentage of documents are filtered out. The team mentioned to me they didn't have the chance to measure recall, only latency.



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