Timezone: »

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

Tue Dec 08 07:00 PM -- 11:59 PM (PST) @ None #None

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

Pari Ram (IBM Research)
Dongryeol Lee (Independent Researcher)
Bill 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