python - Diferencia entre scipy.spatial.KDTree y scipy.spatial.cKDTree

Question

¿Cuál es la diferencia entre estos dos algoritmos?

Answer 1

En un caso de uso (5D las búsquedas de vecinos más cercanos en un KDTree con aproximadamente 100K puntos) cKDTree es aproximadamente 12 veces más rápido que KDTree.

Answer 2

cKDTree es un subconjunto de KDTree , implementado en C ++ KDTree en Cython, por lo tanto, más rápido.

Cada uno de ellos es

un trie binario, cada uno de cuyos nodos representa un hiperrectangle alineado con el eje. Cada nodo especifica un eje y divide el conjunto de puntos en función de si su coordenada a lo largo de ese eje es mayor o menor que un valor particular.

pero KDTree

también admite consultas de todos los vecinos, tanto con matrices de puntos como con otros kd-trees. Estos utilizan un algoritmo razonablemente eficiente, pero el árbol kd no es necesariamente la mejor estructura de datos para este tipo de cálculo.