2D 空間のポイントを表す約 100,000 (X, Y) ペアのデータセットがあります。各点について、その k 最近傍点を見つけたいと思います。
それで、私の質問は、全体の実行時間を絶対に最小限に抑えたいと仮定すると、どのデータ構造/アルゴリズムが適切な選択になるでしょうか?
私はコードを探しているのではなく、適切なアプローチへの単なるポインタです。関連性があると思われる選択肢の範囲 (四分木、R 木、kd 木など) に少し戸惑っています。
最良のアプローチは、データ構造を構築してから、各ポイントに対してある種の k 最近傍検索を実行することだと考えています。ただし、(a) 事前にポイントを知っており、(b) すべてのポイントの検索を 1 回だけ実行する必要があることを知っているので、おそらくより良いアプローチがあるでしょうか?
追加の詳細:
kが比較的小さく（<20程度）、分布がほぼ均一である場合は、ポイントが含まれる範囲をオーバーレイするグリッドを作成し、グリッドあたりの平均ポイント数がkよりも快適に多くなるように選択します（中央に配置されたポイントは、通常、その1つのグリッドポイントでk近傍を取得します）。次に、各軸に沿って最初の（オーバーラップする）グリッドから半分離れた他のグリッドのセットを作成します。次に、各ポイントについて、どのグリッド要素に分類されるかを計算し（グリッドは規則的であるため、検索は必要ありません）、そのポイントが中心に最も近い4つ（または重複するグリッド）の1つを選択します。
各グリッド要素内で、ポイントは1つの座標（たとえばx）で並べ替える必要があります。選択した要素から始めて（二等分線を使用して見つけます）、k個のアイテムが見つかるまで、並べ替えられたリストに沿って外側に歩きます（ここでも、kが小さい場合、k個のベストヒットのリストを維持する最も速い方法は、バイナリ挿入ソートを使用することです。 、挿入時に最悪の一致が最後から外れるようにします。挿入ソートは通常、最新のハードウェアで最大約30項目まで他のすべてを打ち負かします）。あなたの最も遠い最近傍がxであなたから離れた次の点よりもあなたに近づくまで続けます（つまり、それらのyオフセットを数えないので、これまでに見つかったk番目に近い点よりも近くなる可能性のある新しい点はありません） 。
まだk点がない場合、またはk点があるが、グリッド要素の1つ以上の壁が、k点の最も遠い点よりも対象の点に近い場合は、関連する隣接するグリッド要素を検索に追加します。
O(N*k^2)これにより、定数係数が比較的低い、のようなパフォーマンスが得られるはずです。kが大きい場合、この戦略は単純すぎるため、kdツリーのように、kで線形または対数線形のアルゴリズムを選択する必要があります。