kdツリーからk最近傍を効率的に見つける方法

Question

実際に質問は以前に尋ねられましたが、私の知る限りでは適切な答えが提供されていません。

私はk-dツリーをどのように実装し、それに対する最近傍探索がどのように機能するかを理解しています。しかし、周りを見回しても、k-dツリーを使用してk個の最近傍を非常に効率的に検索する効率的な方法を見つけることはできません。私は、最も近いネイバーを見つけてそれを削除し、プロセスをk-1回繰り返してから、すべての削除されたノードを再びツリーに挿入することしか考えられません。しかし、それは冗長で、目的を完全に打ち破っているようです。

k-dツリーを使用してk最近傍を見つける簡単な方法を探したいだけです。私はそれを可能にするオンライン実装またはライブラリを探していません。私は論理を理解するだけで、それを自分で実装します。

Answer 1

https://en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_searchのアルゴリズムは、「ツリー全体を再帰的に検索する」という最適化と見なすことができ、検索しようとしているサブツリーに現在の最善のネイバーの改善が含まれていない可能性がある場合に最適化が行われます。

これを変更して最近隣のk個のノードを見つけるには、最も近い1個のノードではなくk個のノードを見つけたままにしておき、最も遠いノードまでの距離を記録します。次に、そのサブツリー内の最も近い点が、これらのk近傍のうちの最も遠い点の改善である可能性があるかどうかに基づいて、サブツリーを探索するか、または無視するかを決定する。

ヒープなどのデータ構造が必要な場合は、k個のアイテムを保持し、距離の値が最も高いアイテムを見つけ出し、そのアイテムを削除し、新たに見つかったアイテムを挿入できます。