Linear-Time Algorithms for Pairwise Statistical Problems
Abstract
Several key computational bottlenecks in machine learning involve pairwise distance computations, including all-nearest-neighbors (finding the nearest neighbor(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, bichromatic case for these problems, in addition to the scientific problem of N-body potential calculation. In this paper we show for the first time O(N) worst case runtimes for practical algorithms for these problems based on the cover tree data structure (Beygelzimer, Kakade, Langford, 2006).
Cite
Text
Ram et al. "Linear-Time Algorithms for Pairwise Statistical Problems." Neural Information Processing Systems, 2009.Markdown
[Ram et al. "Linear-Time Algorithms for Pairwise Statistical Problems." Neural Information Processing Systems, 2009.](https://mlanthology.org/neurips/2009/ram2009neurips-lineartime/)BibTeX
@inproceedings{ram2009neurips-lineartime,
title = {{Linear-Time Algorithms for Pairwise Statistical Problems}},
author = {Ram, Parikshit and Lee, Dongryeol and March, William and Gray, Alexander G.},
booktitle = {Neural Information Processing Systems},
year = {2009},
pages = {1527-1535},
url = {https://mlanthology.org/neurips/2009/ram2009neurips-lineartime/}
}