我有一个应用程序，其中 Hilbert R-Tree (wikipedia) (citeseer)似乎是一个合适的数据结构。具体来说，它需要对将经历大量更新的数据集进行相当快速的空间查询。
然而，据我所知，该数据结构的算法描述都没有提到如何实际计算所需的希尔伯特值；这是沿希尔伯特曲线到该点的距离。
那么关于如何计算这个有什么建议吗？
user89335
问问题
7385 次
8 回答
9
有趣的问题！
我做了一些谷歌搜索，好消息是，我找到了 Hilbert Value 的实现。
潜在的坏消息是，它在 Haskell 中......
http://www.serpentine.com/blog/2007/01/11/two-dimensional-spatial-hashing-with-space-filling-curves/
它还提出了一个 Lebesgue 距离度量，您可以更轻松地计算。
于 2008-09-19T23:01:28.277 回答
7
下面是我的 Java 代码改编自 Xian Lu 和 Gunther Schrack 发表在 Software: Practice and Experience Vol. 上的论文“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;
}
于 2008-11-24T11:46:52.763 回答
4
于 2008-09-23T07:03:55.160 回答
4
上面的代码和 java 代码适用于 2D 数据点。但对于更高的维度，您可能需要查看 Jonathan Lawder 的论文：JKLawder。使用希尔伯特空间填充曲线计算一维和 n 维值之间的映射。
于 2010-11-27T18:40:43.400 回答
3
我想出了一种更有效的方式来交错位。它可以在斯坦福图形网站上找到。我包含了一个我创建的版本，它可以将两个 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局部变量应该是类常量，但为了简单起见，它保留了这种方式。
于 2009-10-14T15:51:22.580 回答
2
迈克尔，
感谢您的 Java 代码！我对其进行了测试，它似乎工作正常，但我注意到位交错函数在递归级别 7 处溢出（至少在我的测试中，但我使用了长值），因为“n”值是使用最高 OneBit（ )-函数，它返回值而不是最高一位的位置；所以循环不必要地进行了许多交错。
我只是将其更改为以下代码段，之后它运行良好。
int max = Math.max(奇数，偶数);
诠释 n = 0;
而（最大> 0）{
n++;
最大值 >>= 1；
}
于 2008-12-17T13:03:46.750 回答
1
如果您需要具有快速删除/插入功能的空间索引，请查看 PH-tree。它部分基于四叉树，但速度更快，空间效率更高。在内部，它使用 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/
于 2014-12-10T16:41:02.133 回答
-1
建议：空间查询一个好的简单高效的数据结构是多维二叉树。
在传统的二叉树中，只有一个“判别式”；用于确定您是选择左分支还是右分支的值。这可以被认为是一维的情况。
在多维二叉树中，您有多个判别式；连续级别使用不同的判别式。例如，对于二维空间数据，您可以使用 X 和 Y 坐标作为判别式。连续级别将使用 X、Y、X、Y...
对于空间查询（例如查找矩形内的所有节点），您从根开始对树进行深度优先搜索，并在每个级别使用判别式以避免在给定矩形中搜索不包含节点的分支。
这使您可以在每个级别将搜索空间减少一半，从而非常有效地在海量数据集中查找小区域。（顺便说一句，这种数据结构对于部分匹配查询也很有用，即省略一个或多个判别式的查询。您只需在省略判别式的级别上搜索两个分支。）
关于这个数据结构的一篇好论文： http://portal.acm.org/citation.cfm?id= 361007 这篇文章有很好的图表和算法描述：http ://en.wikipedia.org/wiki/Kd-tree
于 2008-09-23T22:50:08.317 回答