Skip to content

Improve connectivity check in HNSW index #6571

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 5 commits into from
May 30, 2025
Merged

Improve connectivity check in HNSW index #6571

merged 5 commits into from
May 30, 2025

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