IEEE Trans Vis Comput Graph. 2021 Aug;27(8):3585-3596. doi: 10.1109/TVCG.2021.3076875. Epub 2021 Jun 30.
Contemporary scientific data sets require fast and scalable topological analysis to enable visualization, simplification and interaction. Within this field, parallel merge tree construction has seen abundant recent contributions, with a trend of decentralized, task-parallel or SMP-oriented algorithms dominating in terms of total runtime. However, none of these recent approaches computed complete merge trees on distributed systems, leaving this field to traditional divide & conquer approaches. This article introduces a scalable, parallel and distributed algorithm for merge tree construction outperforming the previously fastest distributed solution by a factor of around three. This is achieved by a task-parallel identification of individual merge tree arcs by growing regions around critical points in the data, without any need for ordered progression or global data structures, based on a novel insight introducing a sufficient local boundary for region growth.
当代科学数据集需要快速且可扩展的拓扑分析，以实现可视化、简化和交互。在这个领域中，并行合并树构建最近有很多贡献，其中分散式、任务并行或面向 SMP 的算法在总运行时间方面占据主导地位。然而，这些最近的方法都没有在分布式系统上计算完整的合并树，这使得该领域仍然依赖于传统的分治方法。本文介绍了一种可扩展的、并行和分布式的合并树构建算法，其性能比之前最快的分布式解决方案提高了约三倍。这是通过在数据中的关键点周围生长区域来并行识别各个合并树弧来实现的，不需要有序的进展或全局数据结构，这是基于一个新的见解，引入了一个足够的局部边界来进行区域生长。
