**Alexander G. Gray and Andrew W. Moore**

The *N*-body problem of computational physics and the all-nearest-neighbors
problem of computational geometry can be considered part of this
class. In this work we focus on six examples of all-point-pairs
problems within statistical learning: nearest-neighbor classification,
kernel density estimation, outlier detection, the two-point
correlation, the multiple two-point correlation,
and the *n*-point correlation.

The last two of these are actually examples of important generalizations
beyond the standard all-point-pairs
problems, which are more difficult. In particular the
n-point correlation is an example of an n-tuple *N*-body problem. It
is naively an *O*(*N*^{n}) computation and thus has
previously been considered computationally intractable for useful
scientific analysis.

We show that, for uniform data (a pessimistic case), our algorithms exhibit favorable asymptotic scaling. Empirically we also show that these methods yield several orders of magnitude in speedup over the naive computation, even for medium-sized datasets. In addition, all the algorithms presented are surprisingly easy to describe and implement.

A second essential idea forming the basis of our approach is that of cached sufficient statistics [1]. The main observation is that one can precompute some sufficient statistics, as appropriate to the computation, and store these in our data structure. The instant availability of these statistics is what allows us, in many cases, to approximate a chunk of data. In the algorithms in which we approximate, we can make our computation arbitrarily close to the precise one, at the cost of efficiency.

Our methods use dual Multiresolution KD-trees, one for each of the two sets of points, performing node-node comparisons rather than the previously used point-node comparisons with a single KD-tree [2]. This is a fundamental advance over the previous methods, which is natural in our current setting in which the query set Q is known in advance. We then have the opportunity to analyze its hyperstructure as well as that of the dataset D, building a separate KD-tree for Q in addition to the one built for D.

[2] Kan Deng and Andrew W. Moore. Multiresolution Instance-Based Learning. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 1995.

[3] Alexander G. Gray and Andrew W. Moore. '*N*-Body' Problems in
Statistical Learning. Advances in Neural Information Processing Systems 13
(Submitted May 2000, Proceedings published May 2001).

This document was generated using the
**LaTeX**2`HTML` translator Version 98.1p1 release (March 2nd, 1998)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:

**latex2html** `-debug -white -no_fork -no_navigation -address -split 0 -dir html -external_file alex alex.tex`.

The translation was initiated by Daniel Nikovski on 2001-01-23