Data structures and algorithms for nearest neighbor search in general metric spaces

By P. Yianilos. 1993

Subfields: Information Retrieval & Search, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Information Retrieval & Search

In Statistical Learning Theory

Citations in the corpus

Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (2016, positive): “This idea has inspired development of many K-NNS and K-ANNS algorithms based on the navigation effect [37-40].”
Fast Interpolation-based t-SNE for Improved Visualization of Single-Cell RNA-Seq Data (2017, methodology): “ementation of t-SNE produces an approximate solution, and can be used on larger datasets. In that implementation, they approximate F attr;i by nearest neighbors as computed using vantage-point trees (Yianilos (1993)). Since the input similarities do not change, they can be precomputed, and hence do ”
Visualizing Large-scale and High-dimensional Data (2016, methodology): “T-SNE constructs the graph using the technique of vantage-point trees [28], the performance of which signiﬁcantly deteriorates when the dimensionality of the data grows high; (2) the eﬃciency of the graph visualization step signiﬁcantly deteriorates when the size of the data becomes large; (3) the…”
Barnes-Hut-SNE (2013, methodology): “Our new algorithm computes a sparse approximation of the similarities between the original data objects using vantage-point trees [31], and subsequently, approximates the forces between the points in the embedding using a Barnes-Hut algorithm [1] — an algorithm commonly used by astronomers to…”
On Aligning Curves (2003, background): “[19], we now show that d is a metric.”
Scalable Nearest Neighbor Algorithms for High Dimensional Data (2014, background): “Example of such decompositions include the hierarchical k-means tree [18], the GNAT [19], the anchors hierarchy [20], the vptree [21], the cover tree [22] and the spill-tree [23].”
Approximate Nearest Neighbor Search on High Dimensional Data - Experiments, Analyses, and Improvement (v1.0) (2016, methodology): “In addition, we also evaluate a classical pivoting partitioning method, Vantage-Point tree [44] (VP-tree), in the experiments.”
Planning algorithms (2006, background): “For more information on efficient nearest-neighbor searching, see the recent survey [478], and [47, 48, 49, 53, 101, 232, 367, 479, 541, 761, 909, 989].”
Permutation Search Methods are Efficient, Yet Faster Search is Possible (2015, background): “VP-tree is a classic space decomposition tree that recursively divides the space with respect to a randomly chosen pivot π[44, 41].”
Singleton indexes for nearest neighbor search (2016, background): “The VPT [29] is a binary tree where each element of the database is either a node or a leaf.”
Learning to Hash for Indexing Big Data—A Survey (2015, methodology): “Tree-based indexing approaches, such as KD tree [4], ball tree [5], metric tree [6], and vantage point tree [7], have been popular during the past several decades.”
Semi-Supervised Hashing for Large-Scale Search (2012, methodology): “The representative tree based algorithms include KD tree [4][5][6], ball tree [7], metric tree [8], and vantage point tree [9].”
Label Partitioning For Sublinear Ranking (2013, methodology): “via locality-sensitive hashing (LSH) (Indyk & Motwani, 1998) or through building a tree (Bentley, 1975; Yianilos, 1993).”
Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform (2006, background): “There is an abundant literature on (approximate) nearest neighbor searching [4–6,8,11–13,16,21,23,24,26,29,30,32,34, 35].”
The Bayesian image retrieval system, PicHunter: theory, implementation, and psychophysical experiments (2000, background): “Inspired by Yianilos's vantage-point tree algorithm, we chose a Monte Carlo approach: sample several random displays from the distribution and choose the one which minimizes .”
Query-driven iterated neighborhood graph search for large scale indexing (2012, methodology): “…trees, including kd-trees [6, 13] and its variants [4, 5, 19, 35], metric trees (e.g., ball trees [24], vantage point trees (vp-tree) [48], spill-trees [23]), and hierarchical k-means trees [29], organize data points using tree structures by recursively partitioning the space into subspaces,…”
Index-driven similarity search in metric spaces (Survey Article) (2003, methodology): “In ball partitioning, the data set is partitioned based on distances from one distinguished object, sometimes called a vantage point [Yianilos 1993], that is, into the subset that is inside and the subset that is outside a ball around the object (e.g., Figure 1(a)).”