octave-ann 1.0

octave-ann is a set of bindings that allow one to use the ANN library from within Octave.

ANN (A Library for Approximate Nearest Neighbor Searching) has some nice data structures and algorithms for computing exact/approx nearest neighbors on an arbitrarily high dimensional point set. Here are bindings that allow one to perform queries like the following from within Octave:

octave:1> ann
octave:2> pts=[-0.297462,0.176102;
0.565538,-0.361496;
0.909313,-0.182785;
0.920712,0.478408;
0.167682,0.0499836;
0.305223,-0.0805835;
0.114973,0.882453;
0.742916,0.16376;
0.0724605,-0.826775;
0.690960,-0.559284;
0.188485,-0.643934;
0.749427,-0.942415;
-0.970662,-0.223466;
0.916110,0.879597;
0.927417,-0.382593;
-0.711327,0.278713;
-0.519172,0.986146;
0.135338,0.924588;
-0.0837537,0.61687;
0.0520465,0.896306];
octave:3> kd=ANNkd_tree(pts);
octave:4> [nn_idx,dd]=kd.annkPriSearch([0.826225,-0.30962],5)
nn_idx =

14 2 1 9 7

dd =

0.015565 0.022991 0.070649 0.080629 0.231029

Where nn_idx contains the row indices of the 5 (approx) nearest neighbors of the given query point ([0.826225,-0.30962] in this case), and dd contains the distance of the given point to each of the returned neighbors. These are computed in at most O(k log(n)) where k is a small constant/parameter that varies with the quality of the approximation. There is no difficulty in dealing with hundreds of dimensions, no constraint on the number of points (other than available memory), and the data structure (kd, above), once constructed, may be used to perform many lookups.

There are several different data structures, algorithms, and parameters available. See the ANN homepage for details. Also there are a number of tests in the bindings/tests/octave directory that can serve as examples. These should be particularly useful since SWIG/Octave doesn't yet provide a way to insert documentation into wrapper code.

Product's homepage