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

Area of Science:

• Computer Science
• Data Science
• Machine Learning

Background:

• Approximate K-nearest neighbor (KNN) search is crucial for large-scale data analysis.
• Existing methods often rely on multiple search structures, increasing complexity.
• Navigable Small World (NSW) graphs offer a graph-based approach but can be further optimized.

Purpose of the Study:

• To propose a novel, fully graph-based approach for approximate KNN search.
• To introduce Hierarchical NSW (HNSW) with controllable hierarchy for improved search efficiency.
• To demonstrate superior performance compared to existing state-of-the-art methods.

Main Methods:

• Developed Hierarchical NSW (HNSW), a multi-layer proximity graph structure.
• Utilized a random layer assignment with exponentially decaying probability for element hierarchy.
• Implemented scale separation and heuristic neighbor selection for performance optimization.

Main Results:

• HNSW achieves logarithmic complexity scaling and outperforms NSW.
• Significant performance gains observed at high recall and with clustered data.
• Demonstrated superior performance over open-source, vector-only state-of-the-art approaches.
• The algorithm's similarity to skip lists enables straightforward distributed implementation.

Conclusions:

• Hierarchical NSW (HNSW) provides an efficient and scalable solution for approximate KNN search.
• The graph-based, multi-layer structure offers distinct advantages over previous methods.
• HNSW is a promising index for large-scale metric space search and distributed systems.