REQ: data structure k-NN matching

[Neel Krishnaswami]

Stuart Reynolds <S.I.Reynolds at cs.bham.ac.uk> wrote:
>
> Does anyone know of an efficient datastructure that supports
> k-nearest-neighbour matching in high-dimensional spaces? It neads to
> be fairly fast (i.e. ideally written in C/C++). I've written my own
> in Python and its way too slow for what I need. If there's one
> already in C/C++, I'd be happy to try to write some Python bindings.

The ANN (Approximate Nearest Neighbor) package is probably what you
want:

  http://www.cs.umd.edu/~mount/ANN/

It's in C++, and I've never used it, but I've heard good things about
it. It should work as long as your distance function is a Minkowski
metric. 


Neel