IEEE Trans Vis Comput Graph. 2020 Jan;26(1):173-183. doi: 10.1109/TVCG.2019.2934257. Epub 2019 Aug 12.
Topological approaches to data analysis can answer complex questions about the number, connectivity, and scale of intrinsic features in scalar data. However, the global nature of many topological structures makes their computation challenging at scale, and thus often limits the size of data that can be processed. One key quality to achieving scalability and performance on modern architectures is data locality, i.e., a process operates on data that resides in a nearby memory system, avoiding frequent jumps in data access patterns. From this perspective, topological computations are particularly challenging because the implied data structures represent features that can span the entire data set, often requiring a global traversal phase that limits their scalability. Traditionally, expensive preprocessing is considered an acceptable trade-off as it accelerates all subsequent queries. Most published use cases, however, explore only a fraction of all possible queries, most often those returning small, local features. In these cases, much of the global information is not utilized, yet computing it dominates the overall response time. We address this challenge for merge trees, one of the most commonly used topological structures. In particular, we propose an alternative representation, the merge forest, a collection of local trees corresponding to regions in a domain decomposition. Local trees are connected by a bridge set that allows us to recover any necessary global information at query time. The resulting system couples (i) a preprocessing that scales linearly in practice with (ii) fast runtime queries that provide the same functionality as traditional queries of a global merge tree. We test the scalability of our approach on a shared-memory parallel computer and demonstrate how data structure locality enables the analysis of large data with an order of magnitude performance improvement over the status quo. Furthermore, a merge forest reduces the memory overhead compared to a global merge tree and enables the processing of data sets that are an order of magnitude larger than possible with previous algorithms.
拓扑数据分析方法可以回答关于标量数据中内在特征的数量、连通性和规模的复杂问题。然而，许多拓扑结构的全局性质使得它们在大规模计算时具有挑战性，因此通常限制了可以处理的数据量。在现代架构上实现可扩展性和性能的一个关键质量是数据局部性，即一个过程在位于附近内存系统中的数据上运行，避免数据访问模式的频繁跳转。从这个角度来看，拓扑计算特别具有挑战性，因为隐含的数据结构表示可以跨越整个数据集的特征，通常需要全局遍历阶段，从而限制了它们的可扩展性。传统上，昂贵的预处理被认为是可以接受的折衷方案，因为它可以加速所有后续查询。然而，大多数已发布的用例仅探索所有可能查询的一小部分，通常是那些返回小的、局部特征的查询。在这些情况下，大部分全局信息未被利用，但计算它占据了总体响应时间的主导地位。我们针对合并树（拓扑结构中最常用的结构之一）解决了这一挑战。特别是，我们提出了一种替代表示形式，即合并森林，它是对应于域分解中区域的局部树的集合。局部树通过桥集连接，允许我们在查询时恢复任何必要的全局信息。由此产生的系统结合了（i）实践中线性扩展的预处理和（ii）快速运行时查询，这些查询提供了与全局合并树的传统查询相同的功能。我们在共享内存并行计算机上测试了我们方法的可扩展性，并展示了数据结构局部性如何使我们能够分析比现有算法能够处理的大一个数量级的数据，从而实现性能提高一个数量级。此外，与全局合并树相比，合并森林减少了内存开销，并能够处理比以前的算法可能处理的大一个数量级的数据。
