Efficient k-nearest neighbor graph construction for generic similarity measures

By Wei Dong, Moses Charikar, K. Li. 2011

841 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Optimization & Training, 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 Optimization & Training

In Signal Processing

Citations in the corpus

Billion-Scale Similarity Search with GPUs (2017, methodology): “7 hours of compute [45], using NN-Descent [15].”
UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction (2018, methodology): “Ecient approximate k-nearest-neighbor computation can be achieved via the Nearest-Neighbor-Descent algorithm of [16].”
Learning to Simulate Complex Physics with Graph Networks (2020, methodology): “We implemented the components of the GNS framework using standard deep learning building blocks, and used standard nearest neighbor algorithms (Dong et al., 2011; Chen et al., 2009; Tang et al., 2016) to construct the graph.”
Linear tSNE optimization for the Web (2018, methodology): “Computationally, UMAP follows very closely LargeVis and adopts a kNN descent procedure [6] and Stochastic Gradient Descent minimization of the objective function.”
A more globally accurate dimensionality reduction method using triplets (2018, background): “Nearest-Neighbor-Descent (Dong et al., 2011) has been shown empirically to have O(N1.”
Node Similarity Preserving Graph Convolutional Networks (2020, methodology): “In addition, this has been a well studied problem and in the literature there exist approximation methods that could be used to significantly speedup the computation for larger graphs, such as [4] that presented a divide-and-conquer method via Recursive Lanczos Bisection, or [7] that is inherently s”
Low-Shot Learning with Large-Scale Diffusion (2017, methodology): “Thanks to recent advances in efﬁcient similarity search [10, 23], trading some accuracy against efﬁciency drastically improves the graph construction time.”
FANNG: Fast Approximate Nearest Neighbour Graphs (2016, background): “…e(Pi, Pj) sorted by distance(Pi, Pj) 5 for each edge ej do 6 u← index of end vertex of ej 7 L← length of ej 8 occluded← false 9 for each edge Ek with start vertex Pi do 10 v ← index of end vertex of Ek 11 if distance(Pu, Pv) < L then 12 occluded← true 13 if not occluded then 14 add edge ej to E”
Visualization and analysis of single-cell RNA-seq data by kernel-based similarity learning (2016, methodology): “The first step is to use a state-of-art nearest neighbor search technique kGraph [45].”
Stable Bias: Evaluating Societal Representations in Diffusion Models (2023, positive): “We then extracted each image’s SIFT features [36] and used k-means [34] to quantize them into a codebook representing a visual vocabulary and computed TF-IDF sparse representations and indexed the images using a graph-based approach [23].”
Polysemous Codes (2016, methodology): “Note that the collection that we consider is signiﬁcantly larger than the ones considered in previous works [15,48] on kNN graph.”
Learning Transferable Knowledge Through Embedding Spaces (2019, methodology): “To construct the graph G one can utilize efficient k-NN graph construction methods as in [76], where the assumption is that: a neighbor of a neighbor is more likely to be a neighbor.”
Want to scale in centralized systems? Think P2P (2015, positive): “The goal of this section is to show that approaches proposed independently, for centralized [10] and for decentralized [32, 33, 35, 40, 41] systems, exploit a similar sampling strategy to construct KNN graphs that is motivated by the same scalability concerns.”
Ultra-Scalable Spectral Clustering and Ensemble Clustering (2019, background): “On the one hand, it makes the conventional K-NN approximationmethods [26], [27], [28] (which are typically designed for general graphs with N N affinity matri-”
The Faiss Library (2024, neutral): “These DBMS are at the junction of traditional databases and Approximate Nearest Neighbor Search (ANNS) algorithms.”
Approximate Nearest Neighbor Search on High Dimensional Data - Experiments, Analyses, and Improvement (v1.0) (2016, neutral): “We evaluate Small World Graph [31] (SW(10), IS’14), Hierarchical Navigable Small World [32](HNSW(10), CoRR’16), Rank Cover Tree [23] (RCT(14), TPAMI’15), K-NN graph [16, 15] (KGraph(15), WWW’11), and our diversified proximity graph (DPG(14)).”