KD ツリーを構築したいポイントのセットがあります。しばらくすると、この KDTree に定期的にいくつかのポイントを追加したいと思います。これを scipy 実装で実行する方法はありますか?
ベストアンサー1
kd木の問題は、アップデート用に設計されていない。
（配列ベースのツリーよりも大幅に多くのメモリを必要とするポインタベースの表現を使用する場合）オブジェクトを挿入したり、墓石メッセージなどのトリックを使用して削除したりすることは比較的簡単ですが、そのような変更を行うと木のパフォーマンスを低下させる。
kd-tree を段階的に再調整する良い方法は知りません。1 次元ツリーには、赤黒ツリー、B ツリー、B* ツリー、B+ ツリーなどがあります。これらは、回転軸と異なるソートのため、kd-tree では明らかに機能しません。したがって、結局のところ、kd-tree では、変更を収集し、時々変更を行うのが最善かもしれません。完全なツリー再構築そうすれば、少なくともこの部分の木はかなり良くなるでしょう。
しかし、似たような構造が存在する（私の実験では、kd-treeよりも優れていることが多い！）：R*ツリーバイナリ分割を実行する代わりに、長方形の境界ボックスを使用してオブジェクトを収集し、ツリーを動的なデータ構造にするために多くの考慮が払われました。これも、R* ツリーが R ツリーよりもはるかに優れたパフォーマンスを発揮する点です。kNN 検索の分割がより巧妙で、増分再バランス調整を実行して構造を改善します。