ann is a SWIG-generated python wrapper for the Approximate Nearest Neighbor (ANN) Library (http://www.cs.umd.edu/~mount/ANN/), developed by David M. Mount and Sunil Arya. ann provides an immutable kdtree implementation (via ANN) which can perform k-nearest neighbor and approximate k-nearest neighbor searches.
scikits.ann can be installed via easy_install:
sudo easy_install scikits.ann
if you are on OS X 10.5 or have ANN already installed in /usr/local. If you don't meet either of these criteria, you can install scikits.ann from source:
1. Download the ANN source from http://www.cs.umd.edu/~mount/ANN/.
2. Build the ANN library with
Windows users see Windows Build Instructions.
3. Checkout the ann wrapper source.
4. Edit the [ANN] section in ann/site.cfg so that ANN_ROOT points to a root directory containing include/ and lib/ directories for the ANN include and libANN (e.g. /usr/local if /usr/local/include and /usr/local/lib contain the ANN include and libANN respectively). You can also just edit ANN_INCLUDE and ANN_LIB to list the directories containing the ANN.h include and libANN lib files respectively:
4. Build and install scikits.ann with
python setup.py build python setup.py test sudo python setup.py install
scikits.ann exposes a single class, kdtree that wraps the Approximate Nearest Neighbor library's kd-tree implementation. kdtree has a single (non-constructor) method, knn that finds the indecies (of the points used to construct the kdtree) of the k-nearest neighbors and the squared distances to those points. A little example will probably be much more enlightening:
>>> import scikits.ann as ann >>> import numpy as np >>> k=ann.kdtree(np.array([[0.,0],[1,0],[1.5,2]])) >>> k.knn([0,.2],1) (array([]), array([[ 0.04]])) >>> k.knn([0,.2],2) (array([[0, 1]]), array([[ 0.04, 1.04]])) >>> k.knn([[0,.2],[.1,2],[3,1],[0,0]],2) (array([[0, 1], [2, 0], [2, 1], [1, 2]]), array([[ 0.04, 1.04], [ 1.96, 4.01], [ 3.25, 5. ], [ 1. , 6.25]])) >>> k.knn([[0,.2],[.1,2],[3,1],[0,0]],3) (array([[ 0, 1, 2], [ 2, 0, 1], [ 2, 1, 0], [ 1, 2, -1]]), array([[ 4.00000000e-002, 1.04000000e+000, 5.49000000e+000], [ 1.96000000e+000, 4.01000000e+000, 4.81000000e+000], [ 3.25000000e+000, 5.00000000e+000, 1.00000000e+001], [ 1.00000000e+000, 6.25000000e+000, 1.79769313e+308]]))
Rob Hetland had produced an alternative ANN wrapper using ctypes. It appears to have similar performance to the SWIG wrapper. It's memory usage is smaller for individual instantiations of a kdtree since it doesn't create a copy of the array of points used to initialize the kdtree. I intend to replace the SWIG-based implementation with Robs, as soon as I verify that it works cross-platform. In the mean time, I've attached Robs code below...