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. Additional employment of a heuristic for selecting proximity graph neighbors significantly increases performance at high recall and in case of highly clustered data. Performance evaluation has demonstrated that the proposed general metric space search index is able to strongly outperform previous opensource state-of-the-art vector-only approaches. Similarity of the algorithm to the skip list structure allows straightforward balanced distributed implementation.

13 pages, 15 figures

References in corpus (2)

• CoPhIR: a Test Collection for Content-Based Image Retrieval
• Efficient Large-scale Approximate Nearest Neighbor Search on the GPU

Cited by in corpus (25)

• PinnerSage: Multi-Modal User Embedding Framework for Recommendations at Pinterest
• DeepXML: A Deep Extreme Multi-Label Learning Framework Applied to Short Text Documents
• Large Scale Graph Learning from Smooth Signals
• ERNIE-GeoL: A Geography-and-Language Pre-trained Model and its Applications in Baidu Maps
• Convolutional Embedding for Edit Distance
• Quicker ADC : Unlocking the hidden potential of Product Quantization with SIMD
• Prompt Perturbation in Retrieval-Augmented Generation based Large Language Models
• High-Dimensional Similarity Search with Quantum-Assisted Variational Autoencoder
• Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search
• FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search
• A Revisit on Deep Hashings for Large-scale Content Based Image Retrieval
• Multi-modal Extreme Classification
• Towards Similarity Graphs Constructed by Deep Reinforcement Learning
• FLASH: Randomized Algorithms Accelerated over CPU-GPU for Ultra-High Dimensional Similarity Search
• Link and code: Fast indexing with graphs and compact regression codes
• Learning Item-Interaction Embeddings for User Recommendations
• Private Proximity Retrieval Codes
• Investigating Strategies for Clause Recommendation
• Efficient Image Retrieval via Decoupling Diffusion into Online and Offline Processing
• Fast k-means based on KNN Graph
• Lessons Learned Addressing Dataset Bias in Model-Based Candidate Generation at Twitter
• Graph-based time-space trade-offs for approximate near neighbors
• Hubness Reduction Improves Sentence-BERT Semantic Spaces
• Annotative Indexing
• Relevance Proximity Graphs for Fast Relevance Retrieval