ポイントP（x、y、z）に最も近い頂点を見つけるための効果的なアルゴリズムを探しています。頂点のセットは固定されており、各リクエストには新しいポイント P が付属しています。kd-tree などの既知の方法を試しましたが、どこでも同じ問題が発生しました。P が近い場合はすべて問題なく、検索はいくつかのツリー ノードに対してのみ実行されます。 . ただし、P が十分に離れている場合は、ますます多くのノードをスキャンする必要があり、最終的に速度が許容できないほど遅くなります。私の仕事では、小さな検索半径を指定する能力がありません。そのような場合の解決策は何ですか？
ありがとうイゴール
検索を高速化する1つの可能な方法は、一定の間隔で間隔を空けて配置された多数の直角プリズムに空間を離散化することです。たとえば、スペースを1×1×1単位立方体のロットに分割できます。次に、空間内のポイントをこれらのボリュームに分散します。これにより、ポイントを含むボリュームにポイントを分散する、ポイントの一種の「ハッシュ関数」が提供されます。
これを行ったら、簡単な事前計算手順を実行し、これらのボリュームのそれぞれについて、最も近い空でないボリュームを見つけます。これを行うには、ボリュームから1ステップ離れてから、2ステップ離れてすべてのボリュームをチェックします。
ここで、最近傍検索を実行するには、次のようにします。スペース内のポイントを、それを含むボリュームにハッシュすることから始めます。そのボリュームにポイントが含まれている場合は、それらすべてを繰り返し処理して、最も近いポイントを見つけます。次に、このプロセスの最初のステップで見つけたボリュームごとに、それらのポイントを繰り返し処理して、それらのいずれかが近いかどうかを確認します。結果として得られる最近傍点は、テスト点に最も近い近傍です。
ボリュームに含まれるポイントが多すぎる場合は、それらのボリュームをさらに小さなボリュームに分割し、この同じプロセスを繰り返すことで、このアプローチを改善できます。または、ボリュームごとに1つずつ、小さなkdツリーの束を作成して、最近傍探索を実行することもできます。このように、各kdツリーは元のkdツリーよりもはるかに少ない数のポイントを保持し、各ボリューム内のポイントはすべて最近傍の妥当な候補です。したがって、検索ははるかに高速になるはずです。
この設定は、スペースを8つではなく、より小さな領域の束に分割することを除いて、精神的に八分木に似ています。
お役に立てれば！
これは、使用されるインデックス構造の問題ではなく、クエリの問題です。
データセットから離れるほど、最近傍ははるかにあいまいになります。
したがって、他のインデックスが大いに役立つとは思えません。
ただし、検索にしきい値をプラグインできる場合があります。つまり、「最も近い隣人を見つけますが、最大距離x内にある場合のみ」です。
ユークリッド距離の静的なメモリ内の3次元点二重ベクトルデータの場合、実際にはkdツリーを打ち負かすことは困難です。データを非常に高速に分割するだけです。八分木は時々速いかもしれませんが、ほとんどはウィンドウクエリのためだと思います。
オブジェクトが非常に少ないがクエリが数百万ある場合は、ハイブリッドアプローチを試すことができます。大まかに次のようになります。データセットの凸包上のすべての点を計算します。中心と半径を計算します。クエリポイントがx倍離れている場合（正しいxを計算するには、自分で3D計算を行う必要があります）、最近傍は凸包ポイントの1つである必要があります。次に、再びkdツリーを使用しますが、ハルポイントのみを含むものです。
またはさらに簡単です。各次元の最小/最大点を見つけます。たぶん、いくつかの極値を追加します（x + y、xy、x + z、xy、y + z、yzなど）。したがって、候補の小さなセットを取得します。それで今のところそれが8ポイントであると仮定しましょう。これらの6点の中心と距離を事前に計算します。中心からこれらの8点までの最大距離をmとします。クエリの場合、中心までの距離を計算します。これがmより大きい場合は、最初にこれら6つの候補のうち最も近いものを計算します。次に、kdツリーをクエリしますが、検索をこの距離に制限します。これには、1（近い場合）および7（遠い隣人の場合）の距離計算が必要であり、適切な候補を早期に指定することで、検索を大幅に高速化できます。さらにスピードアップするには、これらの6〜26個の候補をkdツリーに編成して、最適な境界をすばやく見つけます。