如何在范围搜索中使用Morton Order？

Question

如果我有一个数据集,其中键是3D中的点,由3个带符号的64位整数表示.我想使用(排序的)键值存储来存储它们,其中键只是字节数组(但我可以指定一个比较器).我想我可以通过使用位交错将所有这些点转换为字节数组,就像在Z/Morton命令中一样,如在如何计算3D Morton数中那样

除了获取单个点,这可以更简单地完成而无需Morton排序,我想做范围搜索,我在一个与轴对齐的框中搜索.我将A和B分别定义为所有坐标最低的方框角,以及所有坐标最高的对角.

现在我的问题是:

1. 对于在逻辑上介于A和B之间的任何点C,C的Morton数也将介于A和B的Morton数之间吗？(这不是莫顿的命令吗？)

2. 如果1为否,A和B是否可以"舍入"到保证包含C的值？

3. 假设1或2是可能的,搜索返回也指向该框之外,我必须"后过滤"了吗？"错误集"有多大(它取决于搜索的大小或位置)？

4. 整数是否签名的事实会导致问题吗？如果是这样,是否有解决方法？

回顾一下,使用Morton Numbers只是实际问题的一种可能解决方案:当3D点必须映射到一维值时,如何有效地在3D整数空间中进行范围搜索？我希望通过在数据库中执行单个范围选择,使用最小键和最大键来获得A和B之间的所有点,理想情况下,尽可能少地获取框外的点.

Answer 1

4)是的,这个标志会引起一个问题,但要解决这个问题很简单.

在创建Morton数之前,只需将x,y和z的符号位与1进行异或.

为什么会这样(使用1维签名字节代替):

二进制-1是11111111

二进制0是00000000

二进制1是00000001

您想要的顺序是-1,0,1,但当前的二进制顺序是0,1,-1.

-1 XOR 10000000 = 01111111

0 XOR 10000000 = 10000000

1 XOR 10000000 = 10000001

现在您的二进制订单是正确的

Answer 2

看来我必须自己回答我的问题了。答案将与 z 顺序曲线有关，这正是我真正要求的。据我所知，这是：

\n

\n
1. 是的。它总是像 z 阶曲线一样工作。
\n
2. 无关紧要，因为 1) 是正确的。
\n
3. 这取决于该区域有多大以及它在哪里，但最坏的情况是当您实际上包括空间的中心时，而不是当您远离它时。对于任何维度，如果在每个维度中使用深度为 N 位的索引，则存在特殊情况，其中 z 顺序曲线为您提供精确匹配，并且您只能获得搜索框中的点。当满足以下条件时会发生这种情况：
\n
4. 搜索区域的所有维度大小均相同，且为 2 的幂 2^M，其中 0 <= M <= N。
\n
5. 搜索区域是一个与所有轴对齐的超立方体。
\n
6. 搜索区域超立方体角点的所有坐标都是 2^M 的倍数。\n当所有这些条件都满足时，搜索区域与子树节点完全对应，因此完全匹配。不过，在一般情况下，您能做的最好的事情就是找到将容纳所有所需点的最小节点，并将其递归地细分为提供部分匹配的较小节点，达到某个最大所需深度，以获得更好的匹配使用多个查询的成本。找到包含该区域所有角点的最小树节点相当于找到所有角点的莫顿码的公共前缀。当使用单个查询时，返回的区域外的点数是查询的该节点的体积减去搜索区域的体积。
\n
7. 我很确定这是一个问题，但我还没有找到相关信息。
\n

\n

看来我说的不太清楚，所以我会做一点 ASCII ART...

\n

二维中的基本 Z 阶（莫顿阶）曲线如下所示（路径为 A、B、C、D）：

\n

x  0   1\n\n0  A \xe2\x86\x92 B\n     \xe2\x86\x99\n1  C \xe2\x86\x92 D\n

\n

因此，A = (0,0) B = (0,1) C = (1,0) D = (1,1)

\n

现在，二维的基本希尔伯特曲线如下所示（路径为 A、B、C、D）：

\n

x  0   1\n\n0  A   D\n   \xe2\x86\x93   \xe2\x86\x91\n1  B \xe2\x86\x92 C\n

\n

因此，A = (0,0) B = (1,0) C = (1,1) D = (0,1)

\n

对于 Z 顺序（莫顿顺序），曲线将从最低点 A (0,0) 开始，到最高点 D (1,1) 结束，同时覆盖其间的所有点。这使得范围搜索变得容易，并且它也可以在 3D 中工作。3D 框中 (0,0,0) 到 (1,1,1) 中的所有点均位于 (0,0,0) 和 (1,1,1) 的 Morton 阶码之间。

\n

对于希尔伯特曲线，从 (0,0) 开始，到 (0,1) 结束（在 3D 中可能类似）。因此，从(0,0)到(1,1)的希尔伯特码执行范围查询将不会找到所有点。

\n

因此，如果我要使用希尔伯特曲线来执行 3D 框 (0,0,0) 到 (1,1,1) 的范围查询（作为单个数据库查询），我需要一个函数来告诉我什么我应该使用点作为第一个点，以及我应该使用哪个点作为最后一个点，因为 (0,0,0) 和 (1,1,1)不起作用。

\n

那么，是否有这样一个函数，您可以在其中给出 8（对于 3D）框坐标，并返回在范围查询中使用的第一个和最后一个点？如果没有它，我就无法使用希尔伯特曲线来解决我的问题。

\n

或者，在伪 SQL 中：

\n

莫顿查询：

\n

SELECT key,data FROM table WHERE (key >= Morton(lowest(box))) AND (key <= Morton(highest(box)))\n

\n

希尔伯特查询：

\n

SELECT key,data FROM table WHERE (key >= Hilbert(XXX(box))) AND (key <= Hilbert(YYY(box)))\n

\n

所以我需要 XXX() 和 YYY()。

\n

[编辑] 这个答案的一部分是针对其他一些答案，告诉我使用希尔伯特曲线，但后来删除了他们的答案。

\n