Pranshu-S commented on PR #16731: URL: https://github.com/apache/lucene/pull/16731#issuecomment-6441905263
> 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). Yes, to address this, I defined two forms of recall (details in https://github.com/apache/lucene/issues/16817, I missed adding it here): - Distinct Recall@10 — I collect the top 500 results per query and map each one to the distinct vector it carries. I drop repeats and keep the first 10 distinct vectors. Then I compare those against the true 10 nearest distinct vectors, found by brute force over the 1,000 unique vectors - Tie-aware Document Recall@10 — I take the top 10 ranked docs and count how many are correct. A doc counts if its score is at least the exact 10th-best score. Identical vectors score the same, so a different but equally correct duplicate still gets credit. So the baseline isn't penalized for returning a different copy of the same vector. | Workload | Distinct R@10 | Document R@10 (tie-aware) | | --- | --- | --- | | Deduplicated | 1.0000 ± 0.0000 | 1.0000 ± 0.0000 | | Uniform duplicates | 0.9899 ± 0.0015 | 0.9973 ± 0.0006 | | **Skewed duplicates** | **0.4082 ± 0.2416** | **0.3089 ± 0.1921** | | All-unique (ref) | 1.0000 ± 0.0001 | 1.0000 ± 0.0001 | Thing to note - Even tie-aware, baseline R@10 is 0.31. The cause is graph connectivity: in collapsed builds the entry point lands in a large duplicate group that has no level-0 edges out > 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). It is applied, and it is what causes the sink to happen in first place. In selectAndLinkDiverse, a copy's best candidate is its duplicate , which gets selected first. After that, diversityCheck rejects every other candidate c, because the scores are identical. > 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) To clarify the dataset: the 90% isn't concentrated in one vector. It's spread across the 1,000 distinct vectors. The largest group is 1,336 docs (13.4% of the corpus), the median group is 3, the 95th percentile is 26, and 110 vectors appear only once. -- 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]
