使用希尔伯特曲线索引进行范围搜索

Question

我有一个基于this算法的希尔伯特曲线索引。我取两到四个值(纬度、经度、unix格式的时间和一个id代码)并创建一维希尔伯特曲线。

我正在寻找一种方法来使用这些数据来创建边界框查询(即“查找此矩形内的所有ids”)。

我正在寻找一种方法，可以在不将1d希尔伯特代码解码回其组成部分的情况下做到这一点。使用Morton/Z阶曲线似乎更容易做到这一点，但我想知道局部性保持。

我的问题是:如果我创建了一个二维希尔伯特曲线范围(即，我将框的范围转换为希尔伯特曲线，因此x1y1->希尔伯特value1和x2y2-> hilbertvalue2)相应的二维希尔伯特值是否都在它们的范围内？

例如，如果我将(1,2)和(20,30)转换为Hilbert值，然后搜索hilbertvalue1和hilbertvalue2之间的所有值，我解码的所有值是否都在(1,2)和(20，30)之间，或者我是否必须执行额外的转换？

当你有2个以上的维度时，另一个问题是设计一个范围。我能够转换希尔伯特曲线的输入和输出，但我如何确保即使是4d的值也具有落入相同矩形/边界框中的纬度和经度？

谢谢。

Answer 1

我的问题是:如果我创建了一个二维希尔伯特曲线范围(即，我将盒子的范围转换成希尔伯特曲线，所以x1y1-> hilbert value1

x2y2-> hilbertvalue2)对应的二维希尔伯特值是否都在它们的范围内？

答案是否定的。这是使用希尔伯特索引的挑战的一部分。下面是一条曲线示例。您会注意到，曲线上的一个点的索引比包含该点的长方体的顶点要高。浅蓝色框是一个示例，其中顶点具有索引117、122、133、138，但内部(尽管在边界上)是值143。

一种简单的方法是蛮力，即访问搜索区域中的每个单元格并计算这些单元格中的索引。然后编译将在查询中使用的索引范围列表。您可以联接一些范围，并在稍后根据基准测试进行性能优化(许多小范围查询可能比查询较少的较大范围然后再进行筛选所需的时间更长)。我想看到比这更优雅的东西，但还没有看到。

更新:我已经想出了一些比暴力破解技术更优雅的方法，其细节(和一个java库)在https://github.com/davidmoten/hilbert-curve上。简而言之，精确覆盖搜索框的范围的端点都将位于该区域的边界上。如果对区域周长上的所有希尔伯特曲线值进行排序，并从最小的值开始，则可以通过测试曲线上的下一个点是停留在周长上、离开框还是在框内来配对所有范围。

当你有超过2个维度时，一个额外的问题是设计一个范围。我能够转换希尔伯特曲线的输入和输出，但我如何确保即使是4d的值也具有落入相同矩形/边界框中的纬度和经度？

上面描述的周长技术适用于任何数量的维度(但当然会变得更昂贵！)。

​

​

Answer 2

对于2维，您可以将曲线视为基数为4的数字(四元键)，并从左到右进行搜索。