Skip to content

Improve connectivity check in HNSW index#6571

Merged
JojiiOfficial merged 5 commits intopayload-hnsw-links-connectivity-checkfrom
payload-hnsw-links-connectivity-check-improvement
May 30, 2025
Merged

Improve connectivity check in HNSW index#6571
JojiiOfficial merged 5 commits intopayload-hnsw-links-connectivity-checkfrom
payload-hnsw-links-connectivity-check-improvement

Conversation

@JojiiOfficial
Copy link
Contributor

@JojiiOfficial JojiiOfficial commented May 21, 2025 •
edited
Loading

Improves connectivity checking for additional payload links in HNSW.
The changes:

  • Skip connectivity measure for first payload index
  • Improve BFS checking by going through the whole graph
  • Budget for checking instead of skipping first node.

Benchmarks:

H&M Dataset

DEV:

  • Benchmark time: 4m9s (Full benchmark time, not only index building)
  • Mean precision: 0.99994 (vector-db-benchmark)
  • Precision in Qdrant UI: 0.945 +- 0.0766

PR:

  • Benchmark time: ~2m40s
  • Mean precision: 0.9999 (vector-db-benchmark) (0.99994 after review)
  • Precision in Qdrant UI: 0.936 ± 0.0819 (0.942 ± 0.079 after review)
  • Measured time savings: 2m46s (~2m42 after review)

arXiv titles

Dev:

  • Benchmark time: 16m7s (Full benchmark time, not only index building)
  • Mean precision: 0.999256 (vector-db-benchmark)
  • Precision in Qdrant UI: 0.989 ± 0.0313

PR:

  • Benchmark time: 14m30s
  • Mean precision 0.999452 (vector-db-benchmark) (0.999404 after review)
  • Precision in Qdrant UI: 0.983 ± 0.0401 (0.987 ± 0.0336 after review)
  • Measured time savings: 30s (12s after review)

@JojiiOfficial JojiiOfficial force-pushed the payload-hnsw-links-connectivity-check-improvement branch from 8b80da6 to fcbddcf Compare May 21, 2025 10:41
@JojiiOfficial JojiiOfficial force-pushed the payload-hnsw-links-connectivity-check branch from 370cfb3 to 9b6dcaf Compare May 22, 2025 07:16
@JojiiOfficial JojiiOfficial force-pushed the payload-hnsw-links-connectivity-check-improvement branch from 48de644 to 627ab53 Compare May 22, 2025 07:19
@JojiiOfficial JojiiOfficial marked this pull request as ready for review May 30, 2025 09:10
generall
generall reviewed May 30, 2025
View reviewed changes
@JojiiOfficial JojiiOfficial merged commit 1e818e4 into payload-hnsw-links-connectivity-check May 30, 2025
16 checks passed
@JojiiOfficial JojiiOfficial deleted the payload-hnsw-links-connectivity-check-improvement branch May 30, 2025 12:53
@generall generall mentioned this pull request May 30, 2025
Merged
3 tasks
generall added a commit that referenced this pull request Jun 4, 2025
@generall
Merge pull request #6479
bc5b131 
* refactor build_filtered_graph

* utils

* fmt

* implement connectivity estimation

* Improve connectivity check in HNSW index (#6571)

* Use BitVec::fill instead of our custom function
generall added a commit that referenced this pull request Jul 17, 2025
@generall
Merge pull request #6479
52ca4ff 
* refactor build_filtered_graph

* utils

* fmt

* implement connectivity estimation

* Improve connectivity check in HNSW index (#6571)

* Use BitVec::fill instead of our custom function
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@generall generall generall approved these changes

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@JojiiOfficial @generall