7

如果我有一个数据集，其中键是 3D 点，由 3 个有符号 64 位整数表示。而且我想使用（排序的）键值存储来存储它们，其中键只是字节数组（但我可以指定一个比较器）。我想我可以通过使用位交错将所有这些点变成一个字节数组，就像如何计算 3D Morton 数中的 Z/Morton 顺序一样

除了获取单个点（可以在没有 Morton 排序的情况下更简单地完成）之外，我还想做范围搜索，在与轴对齐的框中进行搜索。我将 A 和 B 分别定义为所有坐标最低的框角，以及所有坐标最高的对角。

现在我的问题是：

  1. 对于逻辑上介于 A 和 B 之间的任何点 C，C 的莫顿数是否也在 A 和 B 的莫顿数之间？（这不是莫顿命令的重点吗？）

  2. 如果 1 为否，A 和 B 是否可以“四舍五入”到保证包含 C 的值？

  3. 假设 1 或 2 是可能的，搜索返回是否也指向该框之外，我必须“后过滤”它？“错误集”有多大（它取决于搜索的大小或位置）？

  4. 整数有符号的事实是否会导致问题？如果是这样，是否有解决方法？

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

4

3 回答 3

7

4) 是的，这个标志会引起问题，但解决起来很简单。

在创建莫顿数之前，只需将 x、y 和 z 的符号位与 1 异或即可。

为什么这样做（使用一维有符号字节代替）：

二进制中的 -1 是 11111111

二进制中的 0 是 00000000

二进制中的 1 是 00000001

你想要的顺序是-1、0、1，但是当前的二进制顺序是0、1、-1。

-1 异或 10000000 = 01111111

0 异或 10000000 = 10000000

1 异或 10000000 = 10000001

现在你的二进制顺序是正确的

于 2012-10-11T20:01:19.650 回答
2

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

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

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

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

x  0   1

0  A → B
     ↙
1  C → D

所以，A = (0,0) B = (0,1) C = (1,0) D = (1,1)

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

x  0   1

0  A   D
   ↓   ↑
1  B → C

所以，A = (0,0) B = (1,0) C = (1,1) D = (0,1)

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

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

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

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

或者，在伪 SQL 中：

莫顿查询：

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

希尔伯特查询：

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

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

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

于 2012-10-11T07:04:56.567 回答
-1

尝试将 3 维减少到 1 维通常不会有太多期望。你可以尝试什么：找到主轴（即通过你的点做一条线），然后将点投影到线上。这为您提供了每个点的请求一维值。当您将框的角投影到线上并取这些值的封闭间隔时，您将获得搜索范围。

于 2012-10-12T12:47:52.603 回答