[SciPy-user] Current status of spatial data structures

[Sturla Molden]

First of all: scipy.stat.KDTree is better than my version in the 
Cookbook. Here is what Anne Archibald wrote about it:

"There is now a compiled kd-tree implementation in scipy.spatial. It is
written in cython and based on the python implementation. It supports
only optionally-bounded, optionally-approximate, k-nearest neighbor
queries but runs without any per-point python code. It includes all
the algorithmic optimizations described by the ANN authors (sliding
midpoint subdivision, multiple-entry leaves, updating minimum-distance
calculation, priority search, and short-circuit distance
calculations). I think it's pretty good. The major feature it is
missing, from what people have asked for, is an all-neighbors query."


Note that 'written in cython' means it is compiled to C.

I did not know of libkdtree++ until recently. It is written in C++ with 
the dimension statically defined as a template. This is a severe 
limitation, as a Scipy module would be bloated (even if you limit 
yourself to say d < 22 and single and double precision).

As for C++: I once wrote a version in C++ similar to that in the 
Cookbook. It ended up being slower than my Python prototype. Can you 
demonstrate that libkdtree++ is faster than the Cyton compiled version 
in SVN?

I have not checked, but I hope the KDTree in scipy.spatial supports 
pickling or some other form of serialization, e.g. for use with 
multiprocessing or saving to disk.

The Cookbook KDTree must be changed after the next release. It is not 
that useful anymore.




Regards,

Sturla Molden









On 1/7/2009 9:15 AM, Willi Richert wrote:
> Hi,
> 
> here are some observations regarding the current status of kdtree support in 
> Python:
> 
> - scipy 0.7 includes scipy.spatial and supports spatial searches via KDTree 
> http://docs.scipy.org/doc/scipy/reference/spatial.html
> 
> - the cookbook contains another kdtree version: 
> http://scipy.org/Cookbook/KDTree
> 
> - I have provided Python swig wrappers to the libkdtree++ library 
> (http://libkdtree.alioth.debian.org/). Although the data structure has to be 
> fixed (at compile time of libkdtree++) and thus one has to change the swig 
> bindings if one needs to store a different type of vector, it is by my 
> knowledge the only implementation that allows changes to the kdtree data 
> structure at runtime (add/remove support after initial setup). All the other 
> approaches are "create once/query multiple times" approaches.
> 
> Maybe this is of interest to somebody on this list. The authors of libkdtree++ 
> work towards a dynamic data structure support. If that is accomplished and I 
> have adjusted the Python wrapper, will there be room for another kdtree 
> implementation in scipy.spatial? If yes, I would try to match the interface as 
> closely as possible to the current 
> 
> Regards,
> wr
> _______________________________________________
> SciPy-user mailing list
> SciPy-user at scipy.org
> http://projects.scipy.org/mailman/listinfo/scipy-user