morton有序点的并行四叉树构造

Question

我收集了一个点，[(x1,y1),(x2,y2), ..., (xn,yn)]，这是莫顿排序。我想并行地从这些点构造一棵四叉树。我的直觉是在每个核心上构建一个子树，并将所有子树合并成一个完整的四叉树。有人能提供一些高层次的洞察力或伪代码，我如何才能有效地做到这一点？

Answer 1

首先，对你的计划有一些想法：

• 你确定并行化的构造会有帮助吗？我认为有一个风险，你不会太快。四叉树结构在CPU上相当便宜，因此它将部分地受到内存带宽的约束。并行化可能没有多大帮助，除非您有单独的内存总线，例如，单独的机器。
• 如果您希望并行机器上的构造并行化，那么通过将点集合分割成大小均匀的块来创建单独的四叉树可能是最便宜的。这比其他解决方案有一个很大的优势:当您想要插入更多的点，或者想要查找点时，morton顺序允许您非常有效地确定哪个树包含点(或者应该包含它，以便插入)。对于窗口查询，您可以进行类似的优化，如果查询窗口的'min/min‘和'max/max’角的morton代码位于同一块(子树)中，那么您只需要查询这一棵树。更多的优化是可能的。

如果您真的想在一台机器上创建一个四叉树，那么有几种方法可以有效地拆分您的数据集：

• 遍历所有点并确定全局最小/最大值。然后遍历所有的点，并将它们(假设4个核)分配到每个核心，其中每个核心代表一个象限。通过将数据集分割成4个大小均匀的块，可以很好地并行处理这些步骤，并生成一个与您的数据集完全匹配的四叉树。您将不得不同步插入到树中，但是由于数据集是morton有序的，所以应该有相对较少的锁冲突。
• 在插入过程中，可以完全避免锁碰撞，方法是使象限与Morton坐标对齐，从而使morton曲线(z曲线)只穿过象限边界一次。缺点:树将不平衡，即不可能所有象限包含相同的数据量。这意味着您的CPU可能有相当不同的工作负载，除非您将子树拆分为子树，以此类推，以便更好地分配负载。避免z曲线过象限边界的分裂平面可以在你坐标的morton代码/z码上识别。将z码分成两位，每一位告诉你选择哪一个(子)象限，即00是下/左，01是下/右，10是上/左，11是上/右。因为您的点是morton排序的，所以您可以使用二进制搜索来查找每个象限的块。我意识到这可能听起来很神秘，没有更多的解释。所以也许你可以看看PH树，它本质上是Z序的(morton有序的)四叉树(更多的是“trie”而不是“tree”)。也有一些深入的解释这里和这里 (无耻的自我广告)。PH-Tree具有一些很好的特性，例如固有地将深度限制在64层(64位数)，同时保证小节点(最大4项为2维)；它还保证，就像四叉树一样，任何插入/删除都不会影响到多个节点，并且可能会添加或删除第二个节点。还有一个C++实现这里。