[SciPy-user] Incremental Nearest Neighbor

[Barry Wark]

Willi,

You're right that libANN doesn't allow you to update the kd-tree after
construction. Depending on your use, however, you may find that
re-creating the kd-tree with the new set of points is fast enough. If
you really need to dynamically update a kd-tree, you may want to start
at http://citeseer.ist.psu.edu/procopiuc02bkdtree.html. I've never
used this structure, but the Bkd-tree appears to allow dynamically
updating the set of points while retaining the kd-tree's efficient
query performance. I don't know of any python implementations or
wrappers of the Bkd-tree, however.

barry

On Tue, Apr 8, 2008 at 11:45 PM, Willi Richert <w.richert at gmx.net> wrote:
> Hi,
>
>  I'm looking for a nearest neighbor lib (accessible from Python) which
>  increments on-line adding and removing of training data.
>
>  The best kNN lib I've come across so far is  approximate
>  nearest neighbor library (http://www.cs.umd.edu/~mount/ANN/) together with the
>  Python wrappers created by Barry Wark (posted at scipy-user some time ago).
>  Howerver, that lib only supports batch mode.
>
>  I need an approach with which I can add and remove training samples at
>  run-time, while always being able to classify/test arriving data according to
>  the actual realization of the kNN.
>
>
>  Thanks for any help,
>  wr
>  _______________________________________________
>  SciPy-user mailing list
>  SciPy-user at scipy.org
>  http://projects.scipy.org/mailman/listinfo/scipy-user
>