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) @
in Spotlights »

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

Author Information

Parikshit Ram (IBM Research AI)
Dongryeol Lee (Independent Researcher)
William B March (University of Texas)
Alexander Gray (Skytree Inc. and Georgia Tech)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors