2009 · 47 citations · 17 references
ComputingComputer ScienceAlgorithmsData StructuresMachine LearningComputational ComplexityComputational StatisticsKernel Density EstimationKernel MethodsN-body SimulationsNearest Neighbor SearchCover TreesManifold LearningPairwise Distance EstimationSublinear-time Algorithms
Several key computational bottlenecks in machine learning involve pairwise dis-tance computations, including all-nearest-neighbors (finding the nearest neigh-bor(s) for each point, e.g. in manifold learning) and kernel summations (e.g. in kernel density estimation or kernel machines). We consider the general, bichro-matic case for these problems, in addition to the scientific problem of N-body simulation. In this paper we show for the first timeO(푁) worst case runtimes for practical algorithms for these problems based on the cover tree data structure [1]. 1
17
A fast algorithm for particle simulations
Leslie Greengard, Vladimir Rokhlin · Journal of Computational Physics · 1987 · 4.9K citations
Cover trees for nearest neighbor
Alina Beygelzimer, Sham M. Kakade, John Langford · 2006 · 834 citations
Finding nearest neighbors in growth-restricted metrics
David R. Karger, Matthias Rühl · 2002 · 342 citations