[SciPy-dev] Ball Tree class

Yaroslav Halchenko lists@onerussian....
Thu Dec 3 10:53:21 CST 2009


Hi Jake and SciPy,

I wonder what is the status of this endeavor?

For our little project we need fast search for a spherical neighborhood
in a cloud of points.  Only now I discovered that scipy has KDTree and
cKDTree which could be  used, BUT both interfaces are somewhat
misfit for this simple goal one way or another.

Also I've ran into libkdtree++ library with Python bindings which seems
to do close what I need (just does range search, not sphere but it could
be more or less efficiently computed post-hoc) and do it very
efficiently upon my simple tests: http://libkdtree.alioth.debian.org/
but it is under Artistic License 2.0...  but may be it might be of use
to inspire modification of scipy's ways to interface with the user
;)

And Jake, how are you going along with your project since there were no
follow ups on this thread I wonder if there was any progress?


On Thu, 29 Oct 2009, Jake VanderPlas wrote:

> Hello,
> I've been using scipy.spatial.KDTree for my research, and found it
> very useful.  Recently, though, my datasets have been getting larger -
> upwards of 10,000 points in 1000-2000 dimensions.
> The KDTree starts getting slow with such a
> large dimensionality.  I've addressed this by writing a C++ Ball Tree
> code, and wrapping it using swig and numpy.i.  I've been wanting to
> begin contributing to the scipy project, and I think this would be a
> great place to start.  I'd like to begin the process of adding
> this to the scipy.spatial package.

> A few questions: Is it preferable to have an
> implementation in C rather than C++?  Cython, swig, or hand-wrapped code?
> cKDTree is written in Cython, with C.  Should I stick to that
> convention to maintain uniformity in the scipy.spatial package?
> Please let me know what you think
>   -Jake
> _______________________________________________
> Scipy-dev mailing list
> Scipy-dev@scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-dev


-- 
                                  .-.
=------------------------------   /v\  ----------------------------=
Keep in touch                    // \\     (yoh@|www.)onerussian.com
Yaroslav Halchenko              /(   )\               ICQ#: 60653192
                   Linux User    ^^-^^    [175555]




More information about the SciPy-Dev mailing list