相互距離によって2D/3D点の配列をソートするヒューリスティック

Question

2D、3D、（4D ...）空間の点の配列（例えば、ノードはunstructured mesh）を考えてください。最初は配列内の点のインデックスは、空間内の位置には関係しません。簡単な例では、私はすでにいくつかの最近傍接続グラフを知っていると仮定します。

私は空間内で互いに近い2つの点が類似したインデックス（配列が近い）を持つ可能性を高めるいくつかのヒューリスティックを希望します。

正確な解決策は非常に難しい（おそらくTravelling salesman problemに似ています）と私は理解していますが、正確な解決策は必要ありません。ソリューションの

私のアイデア：

は、いくつかの単純な解決策は次のようになります：

1. for each point "i" compute fitness E_i given by sum of distances in array (i.e. index-wise) from its spatial neighbors (i.e. space-wise) 
    E_i = -Sum_k (abs(index(i)-index(k))) 
    where "k" are spatial nearest neighbors of "i" 
2. for pairs of points (i,j) which have low fitness (E_i,E_j) 
    try to swap them, 
    if fitness improves, accept 

が、詳細な実装とその性能の最適化はそれほど明確ではありません。予め計算された最近傍を必要としません

他の解決策は、私はこのはかなり一般的な問題になると思うし、良い解決策に存在し得るいくつかのLocality-sensitive_hashing

に基づいてされるだろう、私は車輪の再発明する必要はありません。

アプリケーション：

• は、メモリアクセスは、それがsmapleの近くにあるノードを検索し、より具体的には、非構造格子の補間を加速することができ、多くの場合、グラフ・トラバーサル
• のボトルネックであることを考慮すると、キャッシュの局所性を向上させます（例えば、放射基底関数の中心）。

Answer 1

space filling curves（SPC）は、空間内の近接を線形配列にマップする標準的なソリューションです。最も一般的なのはHilbert-curvesとz-curves (Morton order)です。

ヒルベルト曲線は最適な近接マッピングを備えていますが、計算には多少費用がかかります。 Zオーダーは依然として優れたプロキシミティマッピングを持っていますが、計算は非常に簡単です。 zオーダリングでは、各次元のビットをインターリーブするだけで十分です。整数値を仮定すると、64ビット3Dポイント（x、y、z）を持つ場合、z値は$ x_0、y_0、z_0、x_1、y_1、z_1、... x_63、y_63、z_63 $、つまり192ですすべての次元の最初のビットと、それに続くすべての次元の2番目のビットからなるビット値です。あなたの配列がそのz値に従って配列されている場合、スペースに近い点は、通常はも配列内にあります。

Hereは、z値に（merge）値（nBitsPerValueは通常32又は64である）をインターリーブ例関数である：

public static long[] mergeLong(final int nBitsPerValue, long[] src) { 
    final int DIM = src.length; 
    int intArrayLen = (src.length*nBitsPerValue+63) >>> 6; 
    long[] trg = new long[intArrayLen]; 

    long maskSrc = 1L << (nBitsPerValue-1); 
    long maskTrg = 0x8000000000000000L; 
    int srcPos = 0; 
    int trgPos = 0; 
    for (int j = 0; j < nBitsPerValue*DIM; j++) { 
     if ((src[srcPos] & maskSrc) != 0) { 
      trg[trgPos] |= maskTrg; 
     } else { 
      trg[trgPos] &= ~maskTrg; 
     } 
     maskTrg >>>= 1; 
     if (maskTrg == 0) { 
      maskTrg = 0x8000000000000000L; 
      trgPos++; 
     } 
     if (++srcPos == DIM) { 
      srcPos = 0; 
      maskSrc >>>= 1; 
     } 
    } 
    return trg; 
} 

IEEEで符号化された場合にも（浮動小数点値のビットをインターリーブすることができます754、通常は標準のコンピュータにあります）、これは非ユークリッド距離の特性をもたらします。最初に負の値を変換する必要があるかもしれません。here、セクション2.3を参照してください。

EDIT 2つはコメントからの質問に答える：

1）私は、通常の 矩形グリッドのための空間充填曲線を作成する方法を理解します。ただし、浮動小数点数 をランダムに配置した場合、いくつかの点を1つのボックスにマップできます。その場合、アルゴリズムは で動作しますか？

浮動小数点（FP）値を使用する方法はいくつかあります。最も簡単なのは、それらを大きな定数で掛けて整数値に変換することです。たとえば、6桁の精度を維持するために、すべてに10^6を掛けます。

もう1つの方法は、FP値のビットレベル表現を使用して整数に変換することです。これには、精度が失われず、乗算定数を決定する必要がないという利点があります。不利な点は、ユークリッド距離計はもはや機能しないということです。

以下のように動作します。浮動小数点値は無限精度ではなく、64ビットに制限されているということです。したがって、それらは自動的にグリッドを形成する。整数値との違いは、浮動小数点値が2次グリッドを形成するのではなく、長方形が（0,0）からの距離が大きくなるにつれて大きくなる長方形のグリッドであることです。グリッドサイズは、与えられた点でどれくらいの精度が得られるかによって決まります。 （0,0）に近く、精度（= grid_size）は10^-28で、（1,1）に近く、10^-16です。hereを参照してください。この歪んだグリッドには依然として近接マッピングがありますが、距離はもはやユークリッドではありません。すべてのために、すなわち、

public static long toSortableLong(double value) { 
    long r = Double.doubleToRawLongBits(value); 
    return (r >= 0) ? r : r^0x7FFFFFFFFFFFFFFFL; 
} 

public static double toDouble(long value) { 
    return Double.longBitsToDouble(value >= 0.0 ? value : value^0x7FFFFFFFFFFFFFFFL); 
} 

は、これらの変換は、変換後の値の順序を保存：;（あなたは、単にfloatintにキャストすることができ、C++でhereから取られたJava、）ここで

は、変換を行うためのコードです2つのFP値の場合、結果の整数は<、>、=に対して同じ順序になります。非ユークリッドの挙動は、ビット列に符号化された指数によって引き起こされる。前述のように、これはまた、 hereのセクション2.3で議論されていますが、コードはわずかに最適化されていません。

2）私のポイントは空間内で移動した場合、このようなスペース 充填曲線の反復更新を行うにはどのようにいくつかのアルゴリズムがありますか？唯一つの有効な順序が存在する点のすべてのセットのために（すなわち、全体のアレイ毎に リオーダリングせず）

空間充填曲線は、特定の順序を課します。ポイントが移動された場合は、そのポイントのz値で決まる新しい位置にポイントを再挿入する必要があります。

小さな動きは、ある点があなたの配列の同じ「領域」にとどまることが多いということです。したがって、実際に固定配列を使用する場合は、その小さな部分を移動するだけです。

動きのあるオブジェクトがたくさんあり、配列が面倒な場合は、「オブジェクトインデックスの移動」（MX-CIF-quadtreeなど）を調べることができます。私は個人的に私自身のPH-Treeをおすすめできます。これは、ビット配列のradix-quadtreeの一種で、内部の順序付けにzカーブを使用しています。更新（およびその他の操作）は非常に効率的です。しかし、私は大規模なデータセットに対してのみ推奨します。小さなデータセットの場合は、単純なクォッドツリーが通常は十分です。

Answer 2

あなたが解決しようとしている問題は、ポイントpとそのNN qが与えられた場合、qのNNがpであることは真実です。

一点山に高くすることができるように、例えば2つの点がそう他の方法で回避することがより山コストまで底から行く、風景の位置を表すことができるので、ない自明であります（山から下へ）。だから、あなたの事件ではないことを確認してください。

---

TilmannZは既に解決策を提案しているので、私はあなたが言及したLSHに強調したいと思います。私はではないあなたのポイントは本当にの低次元空間にあるので、それは100ではないので、なぜLSHを使用するのですか？

2D NNSのようなCGALのアルゴリズムに行くか、単純なkd-treeのようにします。スピードが重要だがスペースがない場合は、quadtree（3Dのオクトリー）に行くのはなぜですか？私はそれを構築しました、それは8ギガバイトのRAMの10次元を超えていません。

しかし、もし、あなたのデータは、その後、私が使用して示唆し、将来的にはより高次元の空間に属していることを感じる：

1. LSHアンドニ、本当にクールな男から。
2. FLANNであり、別のアプローチを提供する。
3. kd-GeRaFこれは私によって開発されました。