About

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.

Install

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

make

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

Usage

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([[0]]), 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]]))

Alternative Wrappers

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. It does, however, have a memory leak so repeated instantiations of new kdtrees might cause a problem depending on your usage pattern. I've attached Rob's code to this page as ann.tar.gz.