Use hash set for visited nodes in HNSW search? [LUCENE-10404]
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
While searching each layer, HNSW tracks the nodes it has already visited using a BitSet. We could look into using something like IntHashSet instead. I tried out the idea quickly by switching to IntIntHashMap (which has already been copied from hppc) and saw an improvement in index performance.
**Baseline:** 760896 msec to write vectors
**Using IntIntHashMap:** 733017 msec to write vectors
I noticed search performance actually got a little bit worse with the change – that is something to look into.
For background, it's good to be aware that HNSW can visit a lot of nodes. For example, on the glove-100-angular dataset with \~1.2 million docs, HNSW search visits \~1000 - 15,000 docs depending on the recall. This number can increase when searching with deleted docs, especially if you hit a "pathological" case where the deleted docs happen to be closest to the query vector.
---
Migrated from [LUCENE-10404](https://issues.apache.org/jira/browse/LUCENE-10404) by Julie Tibshirani (@jtibshirani), updated Aug 07 2022
Contributor guide
Research direction
Start by locating the HNSW layer-search code that tracks visited nodes with BitSet, then inspect the existing IntIntHashMap copied from hppc. Compare indexing and search performance, including cases with deleted docs and varying recall. Done means the visited-node representation improves or appropriately balances both measured workloads.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- performance, search
- Issue type
- Refactor
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100