An Algorithm for Finding Best Matches in Logarithmic Expected Time

By Jerome H. Friedman, J. Bentley, R. Finkel. 1977

How researchers see this paper

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

In Statistical Learning Theory

Citations in the corpus

Product Quantization for Nearest Neighbor Search (2011, methodology): “( Several multi-dimensional indexing methods, such as the popular KD-tree [5] or other branch and bound techniques, have been proposed to reduce the search time.”
Maximum inner-product search using cone trees (2012, methodology): “e for indexing the points and a branch-and-bound algorithm speciﬁcally for the task of maximum inner-product search. Tree data structures have been widely used for the task of nearest-neighbor search [13, 4, 29]. And even though the task of nearest-neighbor search is slightly diﬀerent from the task ”
Improving Generalization via Scalable Neighborhood Component Analysis (2018, methodology): “For nearest neighbor search at the run time, computation complexity can be mitigated with proper data structures such as ball-trees [7] and quantization methods [16].”
Example-based photometric stereo: shape reconstruction with general, varying BRDFs (2005, methodology): “Several fast algorithms have been developed for nearest-neighbors computations based on k -d trees [1], [5], [11], [23].”
Approximated and User Steerable tSNE for Progressive Visual Analytics (2015, methodology): “A KNN search is computed on all T KD-Trees, while a maximum number of leaves L are visited.”
Reinforcement Learning: An Introduction (1998, background): “Friedman, Bentley, and Finkel (1977) clarified the algorithm for nearest neighbor search with k-d trees.”
Index-driven similarity search in metric spaces (Survey Article) (2003, methodology): “This is the case for a PR quadtree [Orenstein 1982; Samet 1990], PR k-d tree [Orenstein 1982], as well as variants of k-d trees [Bentley 1975] such as the adaptive k-d tree [Friedman et al. 1977] and the BSP tree [Fuchs et al. 1980].”
FAST SEMANTIC SEGMENTATION OF 3D POINT CLOUDS WITH STRONGLY VARYING DENSITY (2016, background): “Beyond the basic k D-tree, a whole family of approximate search techniques exists that are signiﬁcantly faster, including approximate nearest neighbor search with the best-bin-ﬁrst heuristic, and randomized search with multiple bootstrapped k D-trees.”
Structure from motion photogrammetry in physical geography (2016, background): “These binary trees partition multidimensional data to quickly eliminate large search spaces (Bentley, 1975; Friedman et al., 1977).”
The Trimmed Iterative Closest Point algorithm (2002, methodology): “Results of testing the new algorithm are shown.”
Complete Random Forest Based Class Noise Filtering Learning for Improving the Generalizability of Classifiers (2019, methodology): “In these algorithms, the search strategy is bounded by the branches of the search tree, such as the ball tree [43], [44], k-d tree [45], [46], multiple branch tree [47], [48], axis search tree [49], [50], LB tree [51], FkNNUPTI [52] and orthogonal search tree [53].”