python - Scipy で KD ツリーの実装にポイントを追加する方法はありますか

Question

KD ツリーを構築したい一連のポイントがあります。しばらくして、この KDTree に定期的にポイントを追加したいと思います。scipy 実装でこれを行う方法はありますか

Answer 1

kd-trees の問題は、更新用に設計されていないことです。

オブジェクトをいくらか簡単に挿入できますが (配列ベースのツリーよりもかなり多くのメモリを必要とするポインタ ベースの表現を使用する場合)、廃棄メッセージなどのトリックを使用して削除を行うことができますが、そのような変更を行うとツリーのパフォーマンスが低下します。

kd ツリーを段階的に再調整するための良い方法を知りません。1 次元ツリーには、赤黒ツリー、B ツリー、B* ツリー、B+ ツリーなどがあります。これらは、軸が回転し、ソートが異なるため、明らかに kd ツリーでは機能しません。最終的に、kd-tree では、変更を収集し、時々完全なツリーの再構築を行うのが最善かもしれません。そうすれば、少なくともツリーのこの部分はかなり良くなります。

ただし、同様の構造が存在します (私の実験では、kd-tree よりも優れていることがよくあります!): R*-tree . バイナリ分割を実行する代わりに、長方形のバウンディング ボックスを使用してオブジェクトを収集し、ツリーを動的なデータ構造にするために多くの考慮が払われました。これは、R* ツリーが R ツリーよりもはるかに優れたパフォーマンスを発揮する場所でもあります。kNN 検索の分割がはるかに巧妙であり、インクリメンタル リバランスを実行して構造を改善します。