47

What is the difference between these two algorithms?

Benjamin
  • 11,560
  • 13
  • 70
  • 119
  • 1
    also `cKDTree` will be more easily threaded because it may not suffer from the `GIL` (see `scipy.spatial` mailing list for more info). not sure as to which version of `cKDTree` was implemented without the `GIL`. – Trevor Boyd Smith Oct 08 '19 at 00:13

4 Answers4

51

cKDTree is a subset of KDTree, implemented in C++ wrapped in Cython, so therefore faster.

Each of them is

a binary trie, each of whose nodes represents an axis-aligned hyperrectangle. Each node specifies an axis and splits the set of points based on whether their coordinate along that axis is greater than or less than a particular value.

but KDTree

also supports all-neighbors queries, both with arrays of points and with other kd-trees. These do use a reasonably efficient algorithm, but the kd-tree is not necessarily the best data structure for this sort of calculation.

agf
  • 171,228
  • 44
  • 289
  • 238
  • 16
    I am surprised this is not advertised more prominently in the KDTree docs and articles. For my simple (and presumably common) use case of finding neighbours in 3D for around 20,000 points, cKDTree was 40x faster. – pythonjsgeo Aug 17 '15 at 15:16
  • 1
    @agf - cKDTree is actually implemented in C++. will you accept an edit ? – gansub Aug 26 '18 at 08:49
  • @gansub Sure, if you include a link to the source or something else that shows that it's C++. – agf Aug 26 '18 at 13:26
  • @agf - https://github.com/scipy/scipy/blob/master/scipy/spatial/ckdtree.pyx distutils language c++ – gansub Aug 27 '18 at 01:33
  • @gansub That appears to be Cython, not C++? – agf Aug 28 '18 at 02:14
  • @agf - you will need to download scipy module and check the code under scipy/spatial/src. There is a .cxx file there. – gansub Aug 28 '18 at 02:29
  • 1
    @gansub I tracked it down: https://github.com/scipy/scipy/tree/master/scipy/spatial/ckdtree/src – agf Aug 29 '18 at 05:22
  • 2
    What do "all-neighbors queries" look like? I'm guessing it's kind of like a parallelized version asking for the nearest points to many points at once. Can anyone confirm? – Nathan majicvr.com Mar 06 '19 at 16:58
  • 2
    i'm with frank. i do not know what is "all neighbors queries". can you please explain what is "all neighbors queries"? – Trevor Boyd Smith Oct 08 '19 at 00:08
16

In a use case (5D nearest neighbor look ups in a KDTree with approximately 100K points) cKDTree is around 12x faster than KDTree.

Newmu
  • 1,930
  • 1
  • 20
  • 25
  • 2
    Another data point: Finding the two nearest neighbours among 1,640 points in 24-dimensions for around 50,000 test vectors: KDTree - 2m 32s / cKDTree - 360ms. – Matti Wens Sep 10 '18 at 10:18
  • 1
    This answer would be 10x more helpful with speed tests to confirm, and/or the "all-neighbors queries" mentioned by @agf – Nathan majicvr.com Mar 06 '19 at 16:59
3

Update 2022: cKDTree is deprecated

The current (v1.8) SciPy documentation states that scipy.spatial.cKDTree is now deprecated and was replaced by the functionally-identical scipy.spatial.KDTree.

Here is the note:

cKDTree is functionally identical to KDTree. Prior to SciPy v1.6.0, cKDTree had better performance and slightly different functionality but now the two names exist only for backward-compatibility reasons. If compatibility with SciPy < 1.6 is not a concern, prefer KDTree.

divenex
  • 15,176
  • 9
  • 55
  • 55
2

Currently, both have almost same APIs, and cKDTree is faster than KDTree. So, In the near future, SciPy developers are planning to remove KDTree, and cKDTree will be renamed to KDTree in a backwards-compatible way.

Ref: Detailed SciPy Roadmap — SciPy v1.6.0.dev Reference Guide https://docs.scipy.org/doc/scipy/reference/roadmap-detailed.html#spatial

divenex
  • 15,176
  • 9
  • 55
  • 55
Atsushi Sakai
  • 938
  • 10
  • 22