ヒルベルト R ツリーで使用する点のヒルベルト値を計算しますか?

StackOverflow https://stackoverflow.com/questions/106237

  •  01-07-2019
  •  | 
  •  

質問

ヒルベルト R ツリーを使用するアプリケーションがあります。 (ウィキペディア) （サイト観察者） 適切なデータ構造と思われます。具体的には、多くの更新が発生するデータ セットに対して、適度に高速な空間クエリが必要です。

ただし、私が見る限り、このデータ構造のアルゴリズムの説明はまったくありません。 言及 実際に必要な金額を計算する方法 ヒルベルト値;これは、線に沿った距離です ヒルベルト曲線 ポイントへ。

それでは、これを計算する方法について何か提案はありますか?

役に立ちましたか？

解決

楽しい質問！

少しグーグルしてみたところ、良いニュースとして、Hilbert Value の実装が見つかりました。

潜在的に悪いニュースは、それが Haskell にあるということです...

http://www.serpentine.com/blog/2007/01/11/two-Dimensional-spatial-hashing-with-space-filling-curves/

また、より簡単に計算できる可能性のあるルベーグ距離計量も提案されています。

他のヒント

以下は、Software に掲載された Xian Lu と Gunther Schrack による論文「ヒルベルト順序のエンコードとデコード」の C コードを改変した私の Java コードです。実践と体験 Vol.26、1335-46ページ（1996年）。

お役に立てれば。改善は大歓迎です!

マイケル

/**
 * Find the Hilbert order (=vertex index) for the given grid cell 
 * coordinates.
 * @param x cell column (from 0)
 * @param y cell row (from 0)
 * @param r resolution of Hilbert curve (grid will have Math.pow(2,r) 
 * rows and cols)
 * @return Hilbert order 
 */
public static int encode(int x, int y, int r) {

    int mask = (1 << r) - 1;
    int hodd = 0;
    int heven = x ^ y;
    int notx = ~x & mask;
    int noty = ~y & mask;
    int temp = notx ^ y;

    int v0 = 0, v1 = 0;
    for (int k = 1; k < r; k++) {
        v1 = ((v1 & heven) | ((v0 ^ noty) & temp)) >> 1;
        v0 = ((v0 & (v1 ^ notx)) | (~v0 & (v1 ^ noty))) >> 1;
    }
    hodd = (~v0 & (v1 ^ x)) | (v0 & (v1 ^ noty));

    return interleaveBits(hodd, heven);
}

/**
 * Interleave the bits from two input integer values
 * @param odd integer holding bit values for odd bit positions
 * @param even integer holding bit values for even bit positions
 * @return the integer that results from interleaving the input bits
 *
 * @todo: I'm sure there's a more elegant way of doing this !
 */
private static int interleaveBits(int odd, int even) {
    int val = 0;
    // Replaced this line with the improved code provided by Tuska
    // int n = Math.max(Integer.highestOneBit(odd), Integer.highestOneBit(even));
    int max = Math.max(odd, even);
    int n = 0;
    while (max > 0) {
        n++;
        max >>= 1;
    }

    for (int i = 0; i < n; i++) {
        int bitMask = 1 << i;
        int a = (even & bitMask) > 0 ? (1 << (2*i)) : 0;
        int b = (odd & bitMask) > 0 ? (1 << (2*i+1)) : 0;
        val += a + b;
    }

    return val;
}

上記のコードと Java コードは 2D データ ポイントに適しています。しかし、より高い次元については、Jonathan Lawder の論文を参照する必要があるかもしれません。 JKロウダー。ヒルベルト空間充填曲線を使用した 1 次元値と n 次元値の間のマッピングの計算。

ビットをインターリーブするもう少し効率的な方法を考え出しました。それは次の場所で見つけることができます。 スタンフォード グラフィックスの Web サイト. 。2 つの 32 ビット整数を 1 つの 64 ビット長にインターリーブできる、私が作成したバージョンを含めました。

public static long spreadBits32(int y) {
    long[] B = new long[] {
        0x5555555555555555L, 
        0x3333333333333333L,
        0x0f0f0f0f0f0f0f0fL,
        0x00ff00ff00ff00ffL,
        0x0000ffff0000ffffL,
        0x00000000ffffffffL
    };

    int[] S = new int[] { 1, 2, 4, 8, 16, 32 };
    long x = y;

    x = (x | (x << S[5])) & B[5];
    x = (x | (x << S[4])) & B[4];
    x = (x | (x << S[3])) & B[3];
    x = (x | (x << S[2])) & B[2];
    x = (x | (x << S[1])) & B[1];
    x = (x | (x << S[0])) & B[0];
    return x;
}

public static long interleave64(int x, int y) {
    return spreadBits32(x) | (spreadBits32(y) << 1);
}

明らかに、 B そして S ローカル変数はクラス定数である必要がありますが、簡単にするためにこのままにしました。

マイケル、

Java コードをありがとう!テストしたところ、問題なく動作しているようですが、再帰レベル 7 でビット インターリーブ関数がオーバーフローすることに気付きました (少なくともテストでは、長い値を使用しました)。これは、「n」値が、highestOneBit( を使用して計算されているためです) )-関数。最上位 1 ビットの位置ではなく値を返します。そのため、ループは不必要に多くのインターリーブを実行します。

それを次のスニペットに変更しただけで、その後は正常に機能しました。

  int max = Math.max(odd, even);
  int n = 0;
  while (max > 0) {
    n++;
    max >>= 1;
  }

高速な削除/挿入機能を備えた空間インデックスが必要な場合は、PH ツリーを参照してください。これは部分的にクアッドツリーに基づいていますが、より高速でスペース効率が高くなります。内部的には、H カーブより空間特性がわずかに悪い Z カーブを使用しますが、 多くの 計算しやすくなります。

紙： http://www.globis.ethz.ch/script/publication/download?docid=699

Java 実装: http://globis.ethz.ch/files/2014/11/ph-tree-2014-11-10.zip

もう 1 つのオプションは X ツリーです。これもここから入手できます。https://code.google.com/p/xxl/

提案：空間クエリに適したシンプルで効率的なデータ構造は、多次元バイナリ ツリーです。

従来のバイナリ ツリーには、「判別式」が 1 つあります。左の分岐を取るか右の分岐を取るかを決定するために使用される値。これは一次元の場合と考えることができます。

多次元二分木には複数の判別式があります。連続したレベルでは異なる判別式が使用されます。たとえば、2 次元空間データの場合、X 座標と Y 座標を判別式として使用できます。連続したレベルでは X、Y、X、Y... が使用されます。

空間クエリ (四角形内のすべてのノードの検索など) の場合は、ルートから開始してツリーの深さ優先検索を実行し、各レベルで判別式を使用して、指定された四角形内にノードを含まない分岐を下位に検索することを回避します。

これにより、各レベルで検索スペースを半分に削減できる可能性があり、大規模なデータ セット内の小さな領域を非常に効率的に見つけることができます。(ところで、このデータ構造は部分一致クエリにも役立ちます。1 つ以上の判別式を省略するクエリ。判別式を省略したレベルで両方のブランチを検索するだけです。)

このデータ構造に関する優れた論文は次のとおりです。 http://portal.acm.org/quote.cfm?id=361007この記事には、優れた図とアルゴリズムの説明が含まれています。 http://en.wikipedia.org/wiki/Kd-tree

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top