algorithm - Morton 代码对于更高维度是最有效的吗？

Question

对于我当前的输入数据，即 3D 点，我使用Morton 代码来提高访问点列表时的缓存一致性。

我还有一些其他数据是 6D 和 7D。对于这样的维度，莫顿代码仍然是一种很好的技术吗？或者有没有其他的技术？其他空间填充曲线技术在 3D 本身中的计算比 Morton 更复杂，我想知道人们是否使用 6D/7D 或更高的替代技术。

Answer 1

您应该尝试行主索引或行主索引。它们还保留了空间局部性，但即使在更高维度上也可以更有效地计算它们。

您可以在《汇编语言的艺术》第 5 章第 211-216 页一书中更深入地了解行优先索引和列优先索引（但几何意义较小） 。相关章节可在此处在线获取。

还有一篇关于您可以考虑的各种空间索引技术的好论文，包括提到的那些： Samet, H. 2017. Sorting Spatial Data。国际地理百科全书。1-11。

Hilbert 和 Gray index 在这里不是一个选项，因为它们的计算速度比 Morton 慢（它们的大多数实现都包含隐式 Morton 编码）。基本上是一个适当的 Morton（基于查找表或幻数）实现，并且行优先/列优先索引是最快的。