Linear-time Algorithms for Pairwise Statistical Problems

Abstract

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