Efficient And Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs

Abstract

We present a new approach for the approximate K-nearest neighbor search based on navigable small world graphs with controllable hierarchy (Hierarchical NSW, HNSW). The proposed solution is fully graph-based, without any need for additional search structures, which are typically used at the coarse search stage of the most proximity graph techniques. Hierarchical NSW incrementally builds a multi-layer structure consisting from hierarchical set of proximity graphs (layers) for nested subsets of the stored elements. The maximum layer in which an element is present is selected randomly with an exponentially decaying probability distribution. This allows producing graphs similar to the previously studied Navigable Small World (NSW) structures while additionally having the links separated by their characteristic distance scales. Starting search from the upper layer together with utilizing the scale separation boosts the performance compared to NSW and allows a logarithmic complexity scaling.

Stats

• citations1162
• S2 citations—
• github stars0
• HF likes0
• heat score22.99
• arxiv keymalkov2016efficient

Related papers

• Down With The Hierarchy: The 'H' In HNSW Stands For "hubs" (2024)0.00
• Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph (2017)18.20
• Navigable Graphs For High-dimensional Nearest Neighbor Search: Constructions And Limits (2024)4.52
• Revisiting The Index Construction Of Proximity Graph-based Approximate Nearest Neighbor Search (2024)7.16
• Fast Approximate Nearest Neighbor Search With A Dynamic Exploration Graph Using Continuous Refinement (2023)0.00
• A Scalable Solution To The Nearest Neighbor Search Problem Through Local-search Methods On Neighbor Graphs (2017)3.58
• Enhancing HNSW Index For Real-time Updates: Addressing Unreachable Points And Performance Degradation (2024)1.56
• Worst-case Performance Of Popular Approximate Nearest Neighbor Search Implementations: Guarantees And Limitations (2023)5.84