kaivalnp commented on PR #16731: URL: https://github.com/apache/lucene/pull/16731#issuecomment-6422709142
Interesting, thanks for running this @Pranshu-S! I didn't go through all the code, but had a few thoughts from the results: A KNN search [does not differentiate b/w duplicates](https://github.com/apache/lucene/blob/f4cc6ac2097cc7e499310648b83fc366030b3b5c/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphSearcher.java#L311-L315), so a high number of duplicates could make the top-k appear different, even if they're all the same vector? For the baseline, I wonder if the recall measurement considered two documents with the same vector as equivalent? (`KnnGraphTester` uses [docid](https://github.com/mikemccand/luceneutil/blob/7c5dc851abcb04bc03e4c2e5d936aaf0bf318304/src/main/knn/KnnGraphTester.java#L1729) for checking if two documents are equal, not the vector itself). In the dedup-aware candidate, since we have one node per unique vector, and we'd traverse its posting list in-order: we might be reducing some of the non-determinism and the results become closer to baseline (highest score + lowest docid). For graph construction: if a node is linked to its duplicate, I think it cannot have other neighbors due to the [diversity check](https://github.com/apache/lucene/blob/f4cc6ac2097cc7e499310648b83fc366030b3b5c/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java#L554-L560)? (any incoming neighbor has to be closer to the node than existing neighbors). The improved recall + search latency + graph construction time make sense in a dataset that has >= 90% duplicates. However, I feel like the duplicate ratio across docs in a sane dataset would be <10% -- can you perform one run along these lines? (preferably with more vectors, say 100K) Also, the primary motivation for de-duplication was to support multiple HNSW graphs for subsets of documents (i.e. duplicates would mainly lie _within_ a document), and the de-duplication across docs was an added benefit. I've been wanting to explore restricting de-duplication to within a document (some benefits listed in #16595). Another avenue to pursue here (from original https://github.com/apache/lucene/pull/15979#discussion_r3665528522): if a node X being inserted is identified as a duplicate of Y, can we use the neighbors of Y to do a seeded HNSW search? i.e. the de-duplicating flat format provides hints about possible neighbors: which is beneficial with duplicates within a document (e.g. the `index-time-filter` option in the benchmark). -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
