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.
Releases:
9/24/08: Releases of this package are now available only from octave-forge. Latest sources are available via octave-forge SVN.
3/15/08: In Octave package form: ann-1.0.tar.gz.
Note that you must download and install SWIG from SWIG's SVN repository,
and it must be in your PATH when you do pkg install ann-1.0.tar.gz
from Octave.
3/9/08:
octave-ann-030908.tar.gz
(patched ann 1.1.1)
octave-ann-030908.patch.gz
(just the patch)
octave-ann was written by Xavier Delacour. Please send feedback, bugs, and/or patches to xavier dot delacour at gmail dot com.