Fast kNN from python

[Janto Dreijer]

Hi!

I am looking for a Python implementation or bindings to a library that
can quickly find k-Nearest Neighbors given an arbitrary distance
metric between objects. Specifically, I have an "edit distance"
between objects that is written in Python.

I haven't looked at the methods in detail but I think I'm looking for
one of the data structures listed on http://en.wikipedia.org/wiki/Metric_trees
(i.e. vp-trees, cover trees, m-trees or bk trees). But I might be
wrong. An approximate kNN would also work.

If there doesn't exist such an implementation yet, any advice on a
library I can wrap myself would also be appreciated.

Thanks!
Janto

PS Before anyone suggests it, I can't use the library at
http://www.cs.umd.edu/~mount/ANN/ as it assumes Minkowski distance
functions.