apache / apache/lucene

Use hash set for visited nodes in HNSW search? [LUCENE-10404]

Open
#11,440 9 comments 0 reactions 0 assignees View on GitHub
legacy-jira-priority:Minor type:enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.