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.