Timezone: »

Spotlight
Linear-time Algorithms for Pairwise Statistical Problems
Parikshit Ram · Dongryeol Lee · William B March · Alexander Gray

Tue Dec 08 03:35 PM -- 03:36 PM (PST) @

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).