Fast Approximate kNN Graph Construction for High Dimensional Data via Recursive Lanczos Bisection

By Jie Chen, Haw-ren Fang, Y. Saad. 2009

296 citations recorded by the source corpus.

Subfields: Computer Vision and Pattern Recognition, 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 Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

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”
Efficient Label Propagation (2014, background): “Many researchers have proposed efficient approaches for the k-NN graph construction (Chen et al., 2009; Connor & Kumar, 2010; Dong et al., 2011).”
Fast approximate similarity search based on degree-reduced neighborhood graphs (2011, background): “The former problem of constructing a k-NN graph is equivalent to the all-k-nearest-neighbor problem, to which considerable research efforts have been devoted [6, 18].”
Efficient k-nearest neighbor graph construction for generic similarity measures (2011, methodology): “Recursive Lanczos Bisection (RLB)[ 8 ] is a divide-and-conquer method for approximate K-NN graph construction in Euclidean space.”
Efficient Computation of k-Nearest Neighbour Graphs for Large High-Dimensional Data Sets on GPU Clusters (2013, methodology): “Another set of techniques is based on a hybrid of spatial subdivision up to a threshold granularity and small scale brute force evaluation or heuristics for refinement [8] [12] [35].”
Hubs in Space: Popular Nearest Neighbors in High-Dimensional Data (2010, background): “Section 7 explores the impact of hubness on common supervised, semi-supervised, and unsupervi ed machine-learning algorithms, showing that the information provided by hubness can be used toignificantly affect the success of the generated models.”
A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search (2021, methodology): “Given a proximity graph G ′(V ′, E ′) (graph index of an algorithm) and the exact graphG (V , E) on the same dataset, we define graph quality of an index as |E ′⋂E | |E | [21, 26, 97].”