Difference between scipy.spatial.KDTree and scipy.

问题:

What is the difference between these two algorithms?

回答1:

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.

回答2:

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