最速の最近傍アルゴリズム

Question

データ配列内の特定のポイントに最も近いポイントを見つける最速の方法は何ですか？

たとえば、3D空間、ポイントの配列（座標 - （x、y、z））とポイント（xp、yp、zp）があります。 （xp、yp、zp）に最も近い点を見つける必要があります。

私が知る限り、最も遅い方法は線形検索を使用することです。もっと良い解決策はありますか？

任意の補助データの追加が可能です。

Answer 1

オクトリーであなたのポイントを整理することができます。次に、小さなサブセットを検索するだけです。

参照：en.wikipedia.org/wiki/Octree

これは（貴重な学習体験になります）あなた自身を実装することができ、かなり単純なデータ構造である、またはあなたが軌道に乗るためにいくつかの有用なライブラリを見つけることができます。

注：当初私はQuadtree（これは2D用です）と誤って言いました。訂正のために@marcogに感謝します。

Answer 2

私の理解しているquadtreeは2dですが、3dsのものは非常に似ています。これにより検索がスピードアップしますが、オンザフライで実行されている場合は、インデックスを計算するためにはるかに多くの時間が必要になります。インデックスを一度計算してから保存することをお勧めします。すべてのルックアップで外側のクワッドのすべてを把握し、ヒットを探していれば、オレンジ色をピーリングするように見えます。クワッドが小さくなるにつれてスピードが大幅に向上します。すべてがトレードオフです。

Answer 3

適切なデータ構造で編成されていない限り、唯一の方法は線形検索です。

Answer 4

ポイントがランダムに分散されていると仮定するか、ツリーのバランスを保つ方法があると仮定して、O（log（n））時間でこれを行うにはKDツリーを使用します。

http://en.wikipedia.org/wiki/Kd-tree

KDの木は、空間クエリのこの種のために優れている、とも、あなたはクエリ点に最も近いk個の隣人を取得することができます。

Answer 5

1回限りの最近傍クエリーを実行している場合、線形検索は実際には得られる最良のものです。これはもちろん、データが事前構造化されていないと仮定しています。

しかし、たくさんのクエリを実行する場合は、いくつかのspace-partitioning data structuresがあります。これらは構造を形成するためにいくつかの前処理を行いますが、最近隣のクエリに非常に高速に答えることができます。

3D空間を扱っているので、octreesまたはkd-treesのいずれかをお勧めします。適切なバランシングアルゴリズム（例：中央値がうまくいく）を実装すると、Kdツリーはより汎用的で（任意のディメンションで動作します）、オクトリーより効率的になりますが、オクトリーは実装が簡単です。

ANNは、これらのデータ構造を使用して偉大なライブラリですが、また、大幅に高速化されているが、それらは単なる近似しているような小さな誤差を持っておおよそ最近傍クエリーを可能にします。エラーが発生しない場合は、エラー・バウンドを0に設定します。

Answer 6

検索を考慮して「最も速い」方法は、voxelsを使用することです。 1：1の点 - ボクセルマップでは、アクセス時間は一定で、本当に速く、座標原点をボクセル原点（必要に応じて）の中心に移動し、位置を丸めてボクセル配列にアクセスするだけですその値。場合によっては、これは良い選択です。私が前に説明したように、1：1のマップが得難い（あまりにも多くの点、あまりにも小さなボクセルの解像度、余りに多くの空き領域）場合、オクテットはより良いです。

Answer 7

チェックこのアウト..あなたもCLRS計算幾何学の章を参照してくださいすることができます。.. http://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf

Answer 8

私はKD-ツリーは、最近傍検索のfine.Also良い動作します示唆しています。

Answer 9

私はこれを、リアルタイム環境での多くの最近隣の検索にかなり重くする必要がありました。シンプルさとスピードの両方の点でより良いアルゴリズムにヒットしました。

あなたのすべてのポイントを取り、d個のリストにコピーを入れます。ここで、dはスペースの次元数です。あなたの場合3.次元に応じて3つのリストをソートします。これはd（nlog（n））時間を要する。それがデータ構造のためです。

問題のすべてのポイントについて、これらの適切にソートされたリストを各次元で維持します。トリックは定義上、一方向の距離がユークリッド距離以下でなければならないということです。したがって、ある方向の距離が、最も近い既知の点の現在の最も近い距離よりも大きい場合、その点は近づくことはできません。さらに重要なことに、その方向のすべての点は大きくすることはできません。これが2 * d方向に当てはまると、我々は定義により最も近い点を持つ。

各要素について、ソートされたリストにバイナリ検索して、必要なポイントが2つの異なる次元にある可能性が最も近い位置を見つけることができます。数学的に、我々は、場合は、+ X、-X、+ Y、-Yにおける距離（他の寸法を追加しやすい）方向がその点は距離を超えていなければならないことは、ポイントまで最小の既知のユークリッド距離を超えて、それがソートされた配列なのでことを知っています定義上、その方向にその距離を超えると、その方向でより良い答えが得られないので、その方向を中止することができます。しかし、これらの4つの方向で展開するとき、私たちが見つけた最も近い点のユークリッド距離に等しいので、mの値を減らすことができます。

したがって、は、軸ごとにソートされたリストがその軸に従ってソートされている必要があります。これはかなりシンプルです。リストを照会する次に

：

• リスト（DLOG（N））のそれぞれに我々のバイナリ検索。
• 現在の最小距離mがわかります。 （最初は無限大になる可能性があります）
• 各リストについて、正負の方向に移動します。我々が持っている2つの* dの方向のそれぞれについて
• 、
  • 我々は近いポイントを見つけたときメートルを下げ、リストを横断。
• 方向が数学的に無益であることを自分自身を証明
は、我々はそのように検索を停止します。
• 方向が残っていない場合は、最も近い点が見つかりました。

リストをソートしており、リスト内の各方向に検索するポイントを見つける必要があります。私たちは時間複雑度log（n）を維持するためにバイナリ検索を行います。それから私達は現在の最良の距離（無限大）を持っており、私たちが利用できる各方向に移動します。新しいポイントを見つけると、これまでのところ、最も近いポイントを更新します。トリックは、その一方向の距離が現在知られている最近点よりもすぐに終了するということです。

既知の最も近い距離が13である場合、+ x、-x、+ y、-y、方向のチェックは、その方向の距離が最も近い既知の距離距離。現在のmよりもさらに+ xの場合、+ xの残りの値はすべて数学的に遠く離れていることが証明されるためです。より良い点とより良い点が得られれば、検索に必要なスペースの量はますます小さくなります。

ある方向に点がなくなると、その方向は終了します。 直線の1次元に沿った点までの距離がそれ自身mより大きい場合、その方向は終了します。

すべての方向がポイントを持つことが証明されているのは、今までのベストポイントよりも遠くになければならないという解決策です。

- 私たちはmを徐々に減らすので、すべてのアルゴリズムと同様に、高次元ではあまり速く降下しませんが、必要な各次元の距離はすばやく低下します。しかし、一方の次元の距離がこれまでに得られた最良の距離よりも大きい場合、必ずしもそれらの点の残りの部分すべてがその方向では改善できない場合があります。

時間の複雑さは、より優れたものと同じように見えます。しかし、データ構造の簡素化のために、このアルゴリズムは明らかに勝ちます。このアルゴリズムを真剣な候補にする多くのプロパティがあります。記事を更新するときは、ソート済みリストやソート済みリストをソートすることが非常に多いため、本当に良いパフォーマンスでリストを整理することができます。あなたは配列を反復しています。実際のパフォーマンスの実際の面では、ほとんどのデータ構造が吸う。一般的にキャッシングとメモリの配置方法のために、私たちはそのようなことに不可知論的であるはずですが、それは大変重要です。現在の関連データの横にあるデータは、であり、実際にはより多くのデータがより速くです。リスト内でどこを探しているのかを既に知っているならば、バイナリ検索でそれを見つける必要がないため、より迅速に解決することができます。そして、以前の繰り返しの情報をこことそのものから再利用する他の許可されたトリック。そして、追加の次元は基本的に自由です（値がより速く収束しないように保存しますが、これは、同じ半径の円よりも球に無作為に分布した点が多いためです）。

---

public class EuclideanNeighborSearch2D { 
    public static final int INVALID = -1; 
    static final Comparator<Point> xsort = new Comparator<Point>() { 
     @Override 
     public int compare(Point o1, Point o2) { 
      return Double.compare(o1.x, o2.x); 
     } 
    }; 
    static final Comparator<Point> ysort = new Comparator<Point>() { 
     @Override 
     public int compare(Point o1, Point o2) { 
      return Double.compare(o1.y, o2.y); 
     } 
    }; 

    ArrayList<Point> xaxis = new ArrayList<>(); 
    ArrayList<Point> yaxis = new ArrayList<>(); 

    boolean dirtySortX = false; 
    boolean dirtySortY = false; 

    public Point findNearest(float x, float y, float minDistance, float maxDistance) { 
     Point find = new Point(x,y); 

     sortXAxisList(); 
     sortYAxisList(); 

     double findingDistanceMaxSq = maxDistance * maxDistance; 
     double findingDistanceMinSq = minDistance * minDistance; 

     Point findingIndex = null; 

     int posx = Collections.binarySearch(xaxis, find, xsort); 
     int posy = Collections.binarySearch(yaxis, find, ysort); 
     if (posx < 0) posx = ~posx; 
     if (posy < 0) posy = ~posy; 

     int mask = 0b1111; 

     Point v; 

     double vx, vy; 
     int o; 
     int itr = 0; 
     while (mask != 0) { 
      if ((mask & (1 << (itr & 3))) == 0) { 
       itr++; 
       continue; //if that direction is no longer used. 
      } 
      switch (itr & 3) { 
       default: 
       case 0: //+x 
        o = posx + (itr++ >> 2); 
        if (o >= xaxis.size()) { 
         mask &= 0b1110; 
         continue; 
        } 
        v = xaxis.get(o); 
        vx = x - v.x; 
        vy = y - v.y; 
        vx *= vx; 
        vy *= vy; 
        if (vx > findingDistanceMaxSq) { 
         mask &= 0b1110; 
         continue; 
        } 
        break; 
       case 1: //+y 
        o = posy + (itr++ >> 2); 
        if (o >= yaxis.size()) { 
         mask &= 0b1101; 
         continue; 
        } 
        v = yaxis.get(o); 
        vx = x - v.x; 
        vy = y - v.y; 
        vx *= vx; 
        vy *= vy; 
        if (vy > findingDistanceMaxSq) { 
         mask &= 0b1101; 
         continue; 
        } 
        break; 
       case 2: //-x 
        o = posx + ~(itr++ >> 2); 
        if (o < 0) { 
         mask &= 0b1011; 
         continue; 
        } 
        v = xaxis.get(o); 
        vx = x - v.x; 
        vy = y - v.y; 
        vx *= vx; 
        vy *= vy; 
        if (vx > findingDistanceMaxSq) { 
         mask &= 0b1011; 
         continue; 
        } 
        break; 
       case 3: //-y 
        o = posy + ~(itr++ >> 2); 
        if (o < 0) { 
         mask = mask & 0b0111; 
         continue; 
        } 
        v = yaxis.get(o); 
        vx = x - v.x; 
        vy = y - v.y; 
        vx *= vx; 
        vy *= vy; 
        if (vy > findingDistanceMaxSq) { 
         mask = mask & 0b0111; 
         continue; 
        } 
        break; 
      } 
      double d = vx + vy; 

      if (d <= findingDistanceMinSq) continue; 

      if (d < findingDistanceMaxSq) { 
       findingDistanceMaxSq = d; 
       findingIndex = v; 
      } 

     } 
     return findingIndex; 
    } 

    private void sortXAxisList() { 
     if (!dirtySortX) return; 
     Collections.sort(xaxis, xsort); 
     dirtySortX = false; 
    } 

    private void sortYAxisList() { 
     if (!dirtySortY) return; 
     Collections.sort(yaxis,ysort); 
     dirtySortY = false; 
    } 

    /** 
    * Called if something should have invalidated the points for some reason. 
    * Such as being moved outside of this class or otherwise updated. 
    */ 
    public void update() { 
     dirtySortX = true; 
     dirtySortY = true; 
    } 

    /** 
    * Called to add a point to the sorted list without needing to resort the list. 
    * @param p Point to add. 
    */ 
    public final void add(Point p) { 
     sortXAxisList(); 
     sortYAxisList(); 
     int posx = Collections.binarySearch(xaxis, p, xsort); 
     int posy = Collections.binarySearch(yaxis, p, ysort); 
     if (posx < 0) posx = ~posx; 
     if (posy < 0) posy = ~posy; 
     xaxis.add(posx, p); 
     yaxis.add(posy, p); 
    } 

    /** 
    * Called to remove a point to the sorted list without needing to resort the list. 
    * @param p Point to add. 
    */ 
    public final void remove(Point p) { 
     sortXAxisList(); 
     sortYAxisList(); 
     int posx = Collections.binarySearch(xaxis, p, xsort); 
     int posy = Collections.binarySearch(yaxis, p, ysort); 
     if (posx < 0) posx = ~posx; 
     if (posy < 0) posy = ~posy; 
     xaxis.remove(posx); 
     yaxis.remove(posy); 
    } 
} 

---

アップデート：コメント欄で、K-ポイントの問題に関しては。あなたはほとんど変わっていないことに気付くでしょう。関連する唯一のものは、ポイントvが現在のm（findingDistanceMaxSq）よりも小さい場合、そのポイントがヒープに追加され、mの値が、発見位置とユークリッド距離との間のユークリッド距離に等しくなるように設定されたk番目の要素。アルゴリズムの正規バージョンは、k = 1の場合と見なすことができる。我々は、我々が望む1つの要素を探索し、vが近づくと分かったときmを唯一の（k = 1）要素に等しく更新する。

距離の比較は遠く離れているかどうかを知る必要があるだけで、平方根関数のクロックサイクルを無駄にすることはないので、

そして、私は、サイズ制限されたヒープにk要素を格納するための完全なデータ構造があることを知っています。明らかに、配列の挿入は最適ではありません。しかし、あまりにも多くのJava依存apis以外には、明らかにGoogle Guavaが作成するが、その特定のクラスのためのものではなかった。しかし、あなたは、あなたのkがそうでない可能性が高いということであれば、本当に気づかないでしょう。しかし、それは、k-時間で記憶された点の挿入のための時間の複雑さをもたらす。また、要素の発見点からの距離をキャッシュするようなものもあります。

最後に、私がコードをテストするために使用するプロジェクトは、移行中ですので、これをテストすることはできませんでした。しかし、それは確かにあなたがこれを行う方法を示しています：今までのk個の最良結果を保存し、mをk番目の最も近い点までの距離に等しくします。 - それ以外は同じです。

ソースの例。

public static double distanceSq(double x0, double y0, double x1, double y1) { 
    double dx = x1 - x0; 
    double dy = y1 - y0; 
    dx *= dx; 
    dy *= dy; 
    return dx + dy; 
} 
public Collection<Point> findNearest(int k, final float x, final float y, float minDistance, float maxDistance) { 
    sortXAxisList(); 
    sortYAxisList(); 

    double findingDistanceMaxSq = maxDistance * maxDistance; 
    double findingDistanceMinSq = minDistance * minDistance; 
    ArrayList<Point> kpointsShouldBeHeap = new ArrayList<>(k); 
    Comparator<Point> euclideanCompare = new Comparator<Point>() { 
     @Override 
     public int compare(Point o1, Point o2) { 
      return Double.compare(distanceSq(x, y, o1.x, o1.y), distanceSq(x, y, o2.x, o2.y)); 
     } 
    }; 

    Point find = new Point(x, y); 
    int posx = Collections.binarySearch(xaxis, find, xsort); 
    int posy = Collections.binarySearch(yaxis, find, ysort); 
    if (posx < 0) posx = ~posx; 
    if (posy < 0) posy = ~posy; 

    int mask = 0b1111; 

    Point v; 

    double vx, vy; 
    int o; 
    int itr = 0; 
    while (mask != 0) { 
     if ((mask & (1 << (itr & 3))) == 0) { 
      itr++; 
      continue; //if that direction is no longer used. 
     } 
     switch (itr & 3) { 
      default: 
      case 0: //+x 
       o = posx + (itr++ >> 2); 
       if (o >= xaxis.size()) { 
        mask &= 0b1110; 
        continue; 
       } 
       v = xaxis.get(o); 
       vx = x - v.x; 
       vy = y - v.y; 
       vx *= vx; 
       vy *= vy; 
       if (vx > findingDistanceMaxSq) { 
        mask &= 0b1110; 
        continue; 
       } 
       break; 
      case 1: //+y 
       o = posy + (itr++ >> 2); 
       if (o >= yaxis.size()) { 
        mask &= 0b1101; 
        continue; 
       } 
       v = yaxis.get(o); 
       vx = x - v.x; 
       vy = y - v.y; 
       vx *= vx; 
       vy *= vy; 
       if (vy > findingDistanceMaxSq) { 
        mask &= 0b1101; 
        continue; 
       } 
       break; 
      case 2: //-x 
       o = posx + ~(itr++ >> 2); 
       if (o < 0) { 
        mask &= 0b1011; 
        continue; 
       } 
       v = xaxis.get(o); 
       vx = x - v.x; 
       vy = y - v.y; 
       vx *= vx; 
       vy *= vy; 
       if (vx > findingDistanceMaxSq) { 
        mask &= 0b1011; 
        continue; 
       } 
       break; 
      case 3: //-y 
       o = posy + ~(itr++ >> 2); 
       if (o < 0) { 
        mask = mask & 0b0111; 
        continue; 
       } 
       v = yaxis.get(o); 
       vx = x - v.x; 
       vy = y - v.y; 
       vx *= vx; 
       vy *= vy; 
       if (vy > findingDistanceMaxSq) { 
        mask = mask & 0b0111; 
        continue; 
       } 
       break; 
     } 
     double d = vx + vy; 
     if (d <= findingDistanceMinSq) continue; 
     if (d < findingDistanceMaxSq) { 
      int insert = Collections.binarySearch(kpointsShouldBeHeap, v, euclideanCompare); 
      if (insert < 0) insert = ~insert; 
      kpointsShouldBeHeap.add(insert, v); 
      if (k < kpointsShouldBeHeap.size()) { 
       Point kthPoint = kpointsShouldBeHeap.get(k); 
       findingDistanceMaxSq = distanceSq(x, y, kthPoint.x, kthPoint.y); 
      } 
     } 
    } 
    //if (kpointsShouldBeHeap.size() > k) { 
    // kpointsShouldBeHeap.subList(0,k); 
    //} 
    return kpointsShouldBeHeap; 
}