Approximate nearest neighbor algorithm based on navigable small world graphs

By Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, Vladimir V. Krylov. 2014

465 citations recorded by the source corpus.

Subfields: Artificial Intelligence, 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 Artificial Intelligence

In Computer Vision and Pattern Recognition

In Information Retrieval & Search

In Signal Processing

Citations in the corpus

Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (2016, methodology): “Construction phase of the NSW structure can be efficiently parallelized without global synchronization and without mesuarable effect on accuracy [26], being a good choice for distributed search systems.”
Singleton indexes for nearest neighbor search (2016, unknown): “Examples of approximate techniques are [27, 7, 13, 1, 16, 15].”
TensorFuzz: Debugging Neural Networks with Coverage-Guided Fuzzing (2018, methodology): “, 2015), tree-based methods (Bernhardsson, 2012), and Proximity Graph methods (Malkov et al., 2014; aalgo, 2012).”
FANNG: Fast Approximate Nearest Neighbour Graphs (2016, methodology): “In particular, our GPU implementation can deliver 90% recall for queries on a data set of 1 million SIFT descriptors at a rate of over 1.2 million queries per second on a Titan X. Finally we also demonstrate how our method scales to datasets of 5M and 20M entries.”
Approximate Nearest Neighbor Search on High Dimensional Data - Experiments, Analyses, and Improvement (v1.0) (2016, unknown): “We evaluate Small World Graph [31] (SW10, IS’14), Hierarchical Navigable Small World [32](HNSW10, CoRR’16), Rank Cover Tree [23] (RCT14, TPAMI’15), K-NN graph [16, 15] (KGraph15, WWW’11), and our diversified proximity graph (DPG14).”
A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search (2021, methodology): “Dozens of algorithms have been proposed to solve this problem from different optimizations [36, 37, 43, 54, 65, 67, 72].”
Comparative Analysis of Data Structures for Approximate Nearest Neighbor Search (2014, methodology): “Small World A small world method is a variant of a navigable small world graph data structure [9].”
Query-Based Improvement Procedure and Self-Adaptive Graph Construction Algorithm for Approximate Nearest Neighbor Search (2015, methodology): “We have made the comparison of the search properties of the graphs produced by Insert_By_Repairing (parameter  = 9) algorithm with the algorithm of connecting with k-nearest neighbors [5].”
Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time (2023, methodology): “…has been a line of work using Near-neighbor Search techniques such as Locality-sensitive hashing (Gionis et al., 1999) and Graph-based indexing (Malkov et al., 2014) for efficient deep neural network training or inference (Zhang et al., 2018; Chen et al., 2019; 2020a; Kitaev et al., 2020; Chen…”
Finding Near Neighbors Through Local Search (2015, methodology): “The search algorithm for k nearest neigbors of APG as described in [5].”
Towards Neural Theorem Proving at Scale (2018, methodology): “, 2011), and Proximity Graphs (PGs) (Malkov et al., 2014).”
Permutation Search Methods are Efficient, Yet Faster Search is Possible (2015, methodology): “[29] called their method a Small World (SW) graph.”
Near neighbor searching with K nearest references (2015, background): “The generalization of Voronoi diagrams to general metric spaces is called a Dirichlet partition, and there are exact and approximate metric indexes based on it [13,17,38,34,35].”
Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph (2017, methodology): “For dense continuous vectors, various solutions have been proposed such as tree-structure based approaches [2,6,8,17,24,36], hashing-based approaches [18, 20, 23, 32, 40], quantization-based approaches [1, 19, 26, 39], and graph-based approaches [3, 21, 33, 41].”