Make HNSW merges faster
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
### Description
It is well known that when merging segments, HNSW is not merged in linear time. We lose a fair bit of useful information as all the NSWs are effectively thrown away (except for a single graph). This means we have useful distributed work from each segment that is ignored.
Do we think its even possible to improve HNSW?
There is existing research around merging hierarchical graphs, but not specifically HNSW:
- https://arxiv.org/abs/1908.00814
- https://arxiv.org/abs/1912.01059 (how they merge the parallel built graphs, not the GPU focused things)
One other option that comes to my mind is keeping NSW scores and use them on merge. So, taking advantage of a [FINGER](https://www.amazon.science/publications/finger-fast-inference-for-graph-based-approximate-nearest-neighbor-search) type of idea. I am not 100% sold on using this during search as it increases memory usage. But, if we store these in a separate file (not loaded during search) but loaded during merge, we could reduce the number of calculations required.
Of course, all these types of changes require due diligence and do NOT obviate the need of a new algorithm in Lucene that is more page-fault friendly (IVFPQ, SPANN, DiskNN or something).
Contributor guide
Research direction
No source file, test, or entry point is named. Start by locating Lucene’s HNSW segment-merge implementation, then read the cited research on hierarchical graph merging and parallel graph construction. Done means demonstrating a validated approach that preserves useful graph information while improving merge time.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- search
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100