计算希尔伯特 R 树中使用的点的希尔伯特值？

Question

我有一个应用程序，其中希尔伯特 R 树 (wikipedia) (citeseer) 似乎是一个合适的数据结构。 具体来说，它需要对将经历大量更新的数据集进行相当快的空间查询。

然而，据我所知，该数据结构的算法描述都没有提及如何实际计算所需的希尔伯特值； 这是沿着希尔伯特曲线到该点的距离。

那么对于如何计算这个有什么建议吗？

Answer 1

建议：对于空间查询来说，一个好的简单高效的数据结构是多维二叉树。

在传统的二叉树中，有一个“判别式”； 用于确定是采用左分支还是右分支的值。 这可以被认为是一维情况。

在多维二叉树中，有多个判别式； 连续的级别使用不同的判别式。 例如，对于二维空间数据，您可以使用 X 和 Y 坐标作为判别式。 连续级别将使用 X、Y、X、Y...

对于空间查询（例如查找矩形内的所有节点），您从根开始对树进行深度优先搜索，并在每个级别使用判别式以避免向下搜索给定矩形中不包含节点的分支。

这使您可以将每个级别的搜索空间减少一半，从而非常有效地在海量数据集中查找小区域。 （顺便说一句，这种数据结构对于部分匹配查询也很有用，即省略一个或多个判别式的查询。您只需在省略判别式的级别上搜索两个分支。）

关于此数据结构的一篇很好的论文：http://portal.acm.org/itation.cfm?id=361007
这篇文章有很好的图表和算法描述：http://en.wikipedia.org/wiki/Kd -树

Answer 2

如果您需要具有快速删除/插入功能的空间索引，请查看 PH 树。 它部分基于四叉树，但速度更快，空间效率更高。 它在内部使用 Z 曲线，其空间属性比 H 曲线稍差，但更容易计算。

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

Java 实现：http://globis.ethz.ch/files/2014/11/ph-tree-2014-11-10.zip

另一种选择是 X-tree，也可在此处使用：
https://code.google.com/p/xxl/

Answer 3

Michael，

感谢您的 Java 代码！ 我测试了它，它似乎工作正常，但我注意到位交错函数在递归级别 7 溢出（至少在我的测试中，但我使用了长值），因为“n”值是使用最高的OneBit（ )-函数，返回值而不是最高一位的位置； 因此循环会进行不必要的多次交错。

我只是将其更改为以下代码片段，之后效果很好。

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

Answer 4

上面的代码和 java 代码适用于 2D 数据点。 但对于更高维度，您可能需要查看 Jonathan Lawder 的论文：JKLawder。 使用希尔伯特空间填充曲线计算一维和 n 维值之间的映射。

Answer 5

我找到了一种稍微更有效的交错位的方法。 可以在 斯坦福图形网站。 我包含了我创建的一个版本，它可以将两个 32 位整数交错为一个 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 局部变量应该是类常量，但为了简单起见，保留了这种方式。

Answer 6

请参阅 uzaygezen。

Answer 7

有趣的问题！

我做了一些谷歌搜索，好消息是，我找到了希尔伯特值的实现。

潜在的坏消息是，它是在 Haskell 中...

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

它还提出了您可能可以更轻松地计算勒贝格距离度量。

Answer 8

下面是我的java代码，改编自Xian Lu和Gunther Schrack发表在Software: Practice and Experience Vol. 11上的论文“Encoding anddecode the Hilbert order”中的C代码。 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;
}