Cover trees for nearest neighbor

By Alina Beygelzimer, Sham M. Kakade, J. Langford. 2006

994 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

Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering (2019, methodology): “There exists data structures for fast NN search in metric spaces such as Cover Trees (Beygelzimer et al., 2006).”
Maximum inner-product search using cone trees (2012, methodology): “Trees have been widely used for nearest-neighbor search [13, 4, 29, 8, 32].”
Barnes-Hut-SNE (2013, background): “Most of these studies focus on speeding up nearest-neighbor searches using space-partitioning (metric) trees ( e.g. , B-trees [2], cover trees [3], and vantage-point trees [31]) or using locality sensitive hashing approaches ( e.g. , [12, 29]).”
Learning to Manipulate Unknown Objects in Clutter by Reinforcement (2015, methodology): “To speed up range search queries, data set Dt is saved in a cover tree (Beygelzimer, Kakade, and Langford 2006), and updated online.”
Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search (2007, methodology): “Previously proposed tree-based indexing methods for KNN search such as R-tree [14], K-D tree [4], SR-tree [18], navigating-nets [19] and cover-tree [5] return accurate re-sults, but they are not time eﬃcient for data with high (intrinsic) dimensionalities.”
Distance Metric Learning for Large Margin Nearest Neighbor Classification (2005, background): “, 2005; Omohundro, 1987) and cover-trees (Beygelzimer et al., 2006).”
Fast k-Nearest Neighbour Search via Prioritized DCI (2017, methodology): “Examples include navigating nets (Krauthgamer & Lee, 2004), cover trees (Beygelzimer et al., 2006) and rank cover trees (Houle & Nett, 2015), which maintain sets of subsampled data points at different levels of granularity and descend through the hierarchy of neighbourhoods of decreasing radii…”
Accelerating t-SNE using tree-based algorithms (2014, methodology): “, 1977; Silpa-Anan and Hartley, 2008), b-trees (Bayer and McCreight, 1972), cover trees (Beygelzimer et al., 2006), vantage-point trees (Yianilos, 1993), and trees constructed using hierarchical clustering (Fukunaga and Narendra, 1975; Brin, 1995; Nister and Stewenius, 2006).”
Linear-time Algorithms for Pairwise Statistical Problems (2009, methodology): “(Growth bound) For allp ∈ ℛ and > 0, if there exists a pointr ∈ ℛ such that 2 d(p, r) ≤ 3 , then∣B(p, 4 )∣ ≥ ( 1 + 1 c2 ) ∣B(p, )∣ .”
Contextual Memory Trees (2018, background): “…(including memory systems that use them (Kaiser et al., 2017)) are computationally inefﬁcient except in special cases (Dasgupta & Sinha, 2015; Beygelzimer et al., 2006) and do not learn. b) Approximate Nearest Neigh-bors via Locality-Sensitive Hashing (Datar et al., 2004) and MIPS…”
Random projection trees and low dimensional manifolds (2008, neutral): “3. ez and ez′ both lie within distance 3Δ/√D of ex0.”
Learning Multi-View Neighborhood Preserving Projections (2011, methodology): “, 1998), navigating nets (Krauthgamer & Lee, 2004) and cover trees (Beygelzimer et al., 2006).”
A learning framework for nearest neighbor search (2007, background): “Nevertheless, we can examine the generalization properties of a data structure learned from one of these classes.”
Fast Neighborhood Graph Search Using Cartesian Concatenation (2013, methodology): “Algorithms, including the KD tree [3, 5, 6, 12], BD trees [3], cover tree [7], nonlinear embedding [17] and so on, have been proposed to improve the search efficiency.”
k-Nearest Neighbour Classifiers - A Tutorial (2020, background): “…( x, z ) ≥ d ( x, y ) + d ( y, z ) ; triangle inequality It is possible to build a k -NN classiﬁer that incorporates an afﬁnity measure that is not a proper metric, however there are some performance optimisations to the basic k -NN algorithm that require the use of a proper metric [42, 9, 53, 53].”
Randomized partition trees for exact nearest neighbor search (2013, neutral): “The more recent cover tree algorithm (Beygelzimer et al., 2006), which has been used quite widely, creates a data structure in space O ( n ) and answers queries in time O (2 d o log n ).”