c++ - 从莫顿有序点构建平行四叉树

Question

我有一组点 [(x1,y1),(x2,y2), ..., (xn,yn)]，它们是 Morton 排序的。我希望从这些点并行构建一个四叉树。我的直觉是在每个核上构造一个子树，然后合并所有的子树，形成一个完整的四叉树。任何人都可以提供一些高级见解或伪代码，我怎样才能有效地做到这一点？

Answer 1

首先考虑一下您的计划:

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

如果你真的想在一台机器上创建一个四叉树，有几种方法可以有效地分割你的数据集:

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