[SciPy-dev] [Numpy-discussion] Proposal: scipy.spatial

Anne Archibald peridot.faceted@gmail....
Sun Oct 12 17:41:47 CDT 2008


2008/10/12 Nathan Bell <wnbell@gmail.com>:
> On Sun, Oct 12, 2008 at 9:43 AM, Anne Archibald
> <peridot.faceted@gmail.com> wrote:
>>
>> 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.
>
> Very nice!  Do you know offhand how much faster the cython
> implementation is for a typical case?

I'm not sure what's "typical" - dimensionality certainly affects the
performance of kd-trees - but it seems to be a speefup by a factor of
20-50:

dimension 3, 10000 points
KDTree constructed:	0.208447
cKDTree constructed:	0.00362301
KDTree 1000 lookups:	0.953508
cKDTree 1000 lookups:	0.0197051
flat cKDTree 1000 lookups:	1.46467

dimension 8, 10000 points
KDTree constructed:	0.394341
cKDTree constructed:	0.00567818
KDTree 1000 lookups:	17.0404
cKDTree 1000 lookups:	0.374597
flat cKDTree 1000 lookups:	2.96095

dimension 16, 10000 points
KDTree constructed:	0.29892
cKDTree constructed:	0.00891495
KDTree 100 lookups:	10.3783
cKDTree 100 lookups:	0.472985
flat cKDTree 100 lookups:	0.667156

These numbers are in seconds; the distribution is a mixture of normal
distributions some moderate distance apart; and the "flat cKDTree"
serves as a somewhat-optimized compiled brute-force search.

Anne
-------------- next part --------------
A non-text attachment was scrubbed...
Name: kdtree_speed.py
Type: text/x-python
Size: 827 bytes
Desc: not available
Url : http://projects.scipy.org/pipermail/scipy-dev/attachments/20081012/a500a78a/attachment.py 


More information about the Scipy-dev mailing list