Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs
By Yury Malkov, Dmitry A. Yashunin. 2016
2,486 citations recorded by the source corpus.
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 (typically used at the coarse search stage of the most proximity graph techniques). Hierarchical NSW incrementally builds a multi-layer structure consisting of a 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 the 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.
Subfields: Computer Networks and Communications, Computer Vision and Pattern Recognition, Information Retrieval & Search, Signal Processing
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computer Networks and Communications
- Ali Farhadi
- Hannaneh Hajishirzi
- Rodrigo Nogueira
- Ce Zhang
- Yuandong Tian
- Beidi Chen
- Tri Dao
- Patrick Lewis
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Dacheng Tao
- Trevor Darrell
- Xiaogang Wang
- Jianfeng Gao
- Jitendra Malik
- Ming-Hsuan Yang
- Chunhua Shen
In Information Retrieval & Search
- Jimmy J. Lin
- Wen-tau Yih
- Sebastian Riedel
- Hannaneh Hajishirzi
- Patrick Lewis
- Danqi Chen
- Akari Asai
- Jinhyuk Lee
In Signal Processing
Citations in the corpus
- Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks (2020, methodology): “1 We use the DPR document encoder to compute document embeddings for each document, and we build a single MIPS index using FAISS [19] using Hierarchical Navigable Small World approximation for efficient retrieval [33], which is then used for all experiments.”
- Real-Time Open-Domain Question Answering with Dense-Sparse Phrase Index (2019, background): “More recently, graph-based search algorithms (Malkov and Yashunin, 2018) have gained popularity as well.”
- openTSNE: a modular Python library for t-SNE dimensionality reduction and embedding (2019, methodology): “Finally, we include the hnswlib (Malkov and Yashunin 2018) library as it provides a third alternative algo-rithm for approximate nearest neighbor search, which may perform better on specific data sets.”
- PAQ: 65 Million Probably-Asked Questions and What You Can Do With Them (2021, methodology): “We use a fast Hierarchical Navigable Small World (HNSW) index in FAISS (Malkov and Yashunin, 2020; Johnson et al., 2019)9 and measure the time required to evaluate the NQ test set on a system with access to one GPU.”
- Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval (2020, methodology): “We implement our system with a fast approximate nearest neighbor search method, i.e. , HNSW (Malkov & Yashunin, 2018), which achieves nearly the same performance as exact search.”
- Pyserini: A Python Toolkit for Reproducible Information Retrieval Research with Sparse and Dense Representations (2021, methodology): “To support dense and hybrid retrieval, Pyserini integrates Facebook’s Faiss library for efficient similarity search over dense vectors [12], which in turns integrates the HNSW library [23] to support low-latency querying.”
- Robust Retrieval Augmented Generation for Zero-shot Slot Filling (2021, methodology): “The passage-vectors are then indexed with an ANN (Approximate Nearest Neighbors) data structure, in this case HNSW (Hierarchical Navigable Small World)(Malkov and Yashunin, 2018) using the open source FAISS library (Johnson et al., 2017)4.”
- Fine-Tuning LLaMA for Multi-Stage Text Retrieval (2023, methodology): “documents are searched within the pre-encoded corpus using an efficient approximate nearest neighbour search library such as HNSW (Malkov and Yashunin, 2020).”
- Generalizing RNA velocity to transient cell states through dynamical modeling (2019, background): “Furthermore, the inferred Only the dynamical model identifies Cr cells to be terminal by assigning no velocity and indicates that OPCs indeed differentiate into OLs.”
- Efficient Passage Retrieval with Hashing for Open-domain Question Answering (2021, methodology): “We also apply two popular post-hoc quantization algorithms to the DPR passage index: simple locality sensitive hashing (LSH) (Neyshabur and Srebro, 2015) and product quantization (PQ) (Jégou et al., 2011).”
- Approximate Nearest Neighbor Search and Lightweight Dense Vector Reranking in Multi-Stage Retrieval Architectures (2020, background): “Approaches based on hierarchical navigable small world (HNSW) graphs [13] represent the current state of the art in ANN search based on a popular benchmark.”
- Milvus: A Purpose-Built Vector Data Management System (2021, methodology): “Existing works on vector data management mainly focus on vector similarity search [14, 20, 22, 33, 35, 39, 45, 46, 48, 49, 57, 65, 68], but they cannot meet the above requirements due to poor performance (on large-scale and dynamic vector data) and limited functionalities (e.g., not being capable…”
- Retrieval-Augmented Generation for AI-Generated Content: A Survey (2024, neutral): “This method ensures that the context before and after the targeted sentence is included, providing a more comprehensive understanding of the retrieved information.”