Pranshu-S commented on issue #16817: URL: https://github.com/apache/lucene/issues/16817#issuecomment-6127055318
To address this bottleneck with sink buildup, I did a rough work of a dedup-aware HNSW build and traversal in PR: https://github.com/apache/lucene/pull/16731. The results came out pretty good but with a challenge of a overhead in latencies and cpu cycles - | Workload | maxConn | Distinct R@10 | Document R@10 (tie-aware) | Mean latency (ms) | | --- | ---: | ---: | ---: | ---: | | Deduplicated | 16 | 1.0000 ± 0.0000 | 1.0000 ± 0.0000 | 0.451 ± 0.008 | | Uniform duplicates | 16 | **1.0000 ± 0.0000** | 1.0000 ± 0.0000 | 0.457 ± 0.019 | | Skewed duplicates | 16 | **0.9895 ± 0.0000** | 1.0000 ± 0.0000 | 0.458 ± 0.018 | | All-unique (ref) | 16 | 1.0000 ± 0.0000 | 1.0000 ± 0.0000 | 1.958 ± 0.073 | Compared that with baseline - | Workload | maxConn | Baseline (plain HNSW) | Candidate (dedup) | Δ (cand − base) | | --- | ---: | ---: | ---: | ---: | | Deduplicated | 16 | 1.0000 ± 0.0000 | 1.0000 ± 0.0000 | +0.000 | | Uniform | 16 | 0.9899 ± 0.0015 | **1.0000 ± 0.0000** | +0.010 | | **Skewed** | 16 | **0.4082 ± 0.2416** | **0.9895 ± 0.0000** | **+0.581** | | All-unique | 16/32 | 1.0000 | 1.0000 | +0.000 | To summarize what it does - **It eliminates the skewed-duplication collapse.** Because large number of similar nodes in the cluster becomes a **single graph node**, traversal is no longer swallowed by redundant copies; it explores distinct neighbors normally. However it comes with some costs which I tried to cut down such as: 1. Identifying the accept-docs for a query when run with filters - since a group node can or cannot contain a doc which passes the filter, eagerly splitting accept-docs to that vectors in the group costed latency increase. Which prompted me to shift it to a bit lazily post filtering 2. Lucene99HnswVectorsWriter writes the nodes as docs come in but that is not feasible for our case because we need to decide during flush if we have enough vectors in a group before we promote it (I have some ideas around -- 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]
