[LUCENE-10054] Handle hierarchy in HNSW graph

• Type: Task
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 9.1
• Labels: vector-based-search
• Lucene Fields: New
• Assignee: Unassigned
• Reporter: Mayya Sharipova
• Created: 18/Aug/21 13:53
• Updated: 18/Sep/23 23:22
• Resolved: 04/Feb/22 19:52

Description

Currently HNSW graph is represented as a single layer graph. 
We would like to extend it to handle hierarchy as per discussion. 

 

TODO tasks:

• add multiple layers in the HnswGraph class
• modify the format in  Lucene90HnswVectorsWriter and Lucene90HnswVectorsReader to handle multiple layers
• modify graph construction and search algorithm to handle hierarchy
• run benchmarks

Issue Links

• links to: GitHub Pull Request #250
• links to: GitHub Pull Request #267
• links to: GitHub Pull Request #416
• links to: GitHub Pull Request #608
• links to: GitHub Pull Request #629
• links to: GitHub Pull Request #699