Difference between scipy.spatial.KDTree and scipy.spatial.cKDTree
Difference between scipy.spatial.KDTree and scipy.spatial.cKDTree
What is the difference between these two algorithms?
2 Answers
2
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 - cKDTree is actually implemented in C++. will you accept an edit ?
– gansub
Aug 26 at 8:49
@gansub Sure, if you include a link to the source or something else that shows that it's C++.
– agf
Aug 26 at 13:26
@agf - github.com/scipy/scipy/blob/master/scipy/spatial/ckdtree.pyx distutils language c++
– gansub
Aug 27 at 1:33
@gansub That appears to be Cython, not C++?
– agf
Aug 28 at 2:14
In a use case (5D nearest neighbor look ups in a KDTree with approximately 100K points) cKDTree is around 12x faster than KDTree.
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.
– Matt Wenham
Sep 10 at 10:18
By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.
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.
– python1981
Aug 17 '15 at 15:16