scipy.spatial.KDTreeとscipy.spatial.cKDTreeの相違点

Question

これら2つのアルゴリズムの違いは何ですか？

Answer 1

cKDTreeは、おそらくCで実装されているKDTreeのサブセットであるため、より高速です。

それらの各々は、そのノードの各々は、軸整列hyperrectangleを表し、

バイナリトライです。各ノードは軸を指定し、その軸に沿った座標が特定の値より大きいか小さいかに基づいて点の集合を分割します。

しかしKDTree

も点の配列とし、他のKDツリーの両方で、すべての隣人のクエリをサポートしています。これらは合理的に効率的なアルゴリズムを使用しますが、この種の計算にはkdツリーが必ずしも最良のデータ構造であるとは限りません。

Answer 2

ユースケース（約100KポイントのKDツリーの5D最寄りルックアップ）では、cKDTreeはKDTreeより約12倍高速です。