[SciPy-user] Current status of spatial data structures
Sturla Molden
sturla at molden.no
Wed Jan 7 08:41:06 EST 2009
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
More information about the SciPy-User
mailing list