# octave-ann 1.0

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

- LICENSE TYPE:
- LGPL (GNU Lesser General Public License)
- USER RATING:
- DEVELOPED BY:
**Xavier Delacour**- HOMEPAGE:
- octave-swig.sourceforge.net
- CATEGORY:
- ROOT \ Science and Engineering \ Mathematics

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:

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.

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.231029octave: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.

Last updated on April 21st, 2008

#### Add your review!

SUBMIT