scikit-learn/scikit-learn — pull request #1732 by jakevdp (2013-03-03 21:21:41+00:00)
Title: MRG: Faster spatial trees with enhancements

New Features
--------------------
- The BallTree class is enhanced to be compatible with 20 different distance metrics. There are also depth first, breadth first, single tree, and dual tree algorithms for the queries. The interface is designed to be fully backward compatible with the old code: all test scripts from previous versions pass on this new version.

- The same core binary tree code which implements the Ball Tree is used to also implement a KD Tree, which can be faster in low dimensions for some datasets.

- Both BallTree and KDTree now have a method for performing fast kernel density estimates in `O[N log(N)]` rather than the naive `O[N^2]`. Six common kernels are
implemented, and each kernel can work with any of the valid distance metrics.

- Both BallTree and KDTree have a method for computing fast 2-point correlation functions, also in `O[N log(N)]` rather than the naive `O[N^2]`. This works with any of the valid distance metrics.

- As a bonus, there is a set of class interfaces to the various distance metrics, with functions to generate a pairwise distance matrix under any of the metrics.

- All functions are documented and tested.

Remaining Tasks
-------------------------
These tasks can be added to this PR, or saved for a later one. I wanted to get some feedback on the changes before going forward with these:
- Update the `NearestNeighbors` classes to use the available metrics, as well as to use the new `KDTree` class

- Rework the narrative documentation for nearest neighbors to reflect these changes.

- Create estimator classes to wrap the kernel density estimator functionality, and perhaps also the 2-point correlation function

Speed
-----------
The speed of the new code is generally faster than the old ball tree implementation and the recent enhancement to the scipy KDTree. Here are some runtimes in seconds for a 2000 pt query on my slightly old linux laptop. The points are in 3 dimensions, with each dimension uniformly distributed between 0 and 1. These timings will change in hard-to-predict ways as the distribution of points is changed. Uniform point distributions in low dimensions tend to favor the KD Tree approach.

```
2000 points, metric = euclidean
Build KNN RNN KDE 2PT
cKDTree 0.00022 0.014
skBallTree 0.00072 0.023 0.022
BallTree 0.0008 0.013 0.011 0.043 0.26
KDTree 0.0011 0.008 0.02 0.031 0.31

2000 points, metric = minkowski (p=3)
Build KNN RNN KDE 2PT
cKDTree 0.00021 0.0088
skBallTree 0.00095 0.029 0.022
BallTree 0.00089 0.017 0.012 0.038 0.18
KDTree 0.0011 0.0095 0.013 0.023 0.2
```