Toward Localized Topological Data Structures: Querying the Forest for the Tree
Toward Localized Topological Data Structures: Querying the Forest for the Tree
复制标题
走向局部拓扑数据结构：从森林中查询树
DOI：
10.1109/tvcg.2019.2934257
复制
发表时间：
2020
影响因子：
5.2
通讯作者：
Pascucci, Valerio
中科院分区：
文献类型：
--
作者：
Klacansky, Pavol;Gyulassy, Attila;Bremer, Peer-Timo;Pascucci, Valerio
数据分析的拓扑方法可以回答有关标量数据中固有特征的数量、连通性和规模的复杂问题。然而，许多拓扑结构的全局性使得它们的计算在规模上具有挑战性，因此往往限制了可以处理的数据的大小。在现代体系结构上实现可伸缩性和性能的一个关键质量是数据局部性，即进程对驻留在附近内存系统中的数据进行操作，从而避免数据访问模式的频繁跳跃。从这个角度来看，拓扑计算特别具有挑战性，因为隐含的数据结构表示可以跨越整个数据集的功能，通常需要全局遍历阶段，从而限制了其可伸缩性。传统上，代价高昂的预处理被认为是一种可接受的权衡，因为它会加速所有后续查询。然而，大多数已发布的用例只研究了所有可能的查询中的一小部分，最常见的是那些返回小的本地特性的查询。在这些情况下，许多全局信息没有被利用，但计算它主导了总体响应时间。我们解决了合并树的这个挑战，合并树是最常用的拓扑结构之一。特别是，我们提出了一种替代表示，即平均森林，即与区域分解中的区域相对应的局部树的集合。局部树由缩略集连接，允许我们在查询时恢复任何必要的全局信息。所得到的系统将(I)在实践中线性扩展的预处理与(Ii)提供与全局合并树的传统查询相同的功能的快速运行时查询相耦合。我们在一台共享内存的并行计算机上测试了我们的方法的可扩展性，并演示了数据结构局部性如何使分析大数据的性能比现状提高了一个数量级。此外，与全局合并树相比，合并森林减少了内存开销，并允许处理比以前的算法可能大一个数量级的数据集。
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, themerge forest, a collection of local trees corresponding to regions in a domain decomposition. Local trees are connected by abridge setthat 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.
登录
查看更多内容
DOI：
--
发表时间：
--
期刊：
--
影响因子：
--
作者：
通讯作者：
--
基于任务的斐波那契堆增强轮廓树
影响因子：
5.3
作者：
Charles Gueunet;P. Fortin;J. Jomier;Julien Tierny
通讯作者：
Julien Tierny
分布式合并树
DOI：
--
发表时间：
2013
期刊：
ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming
影响因子：
--
作者：
D. Morozov;G. Weber
通讯作者：
G. Weber
分布式轮廓树
DOI：
--
发表时间：
2014
期刊：
Topological Methods in Data Analysis and Visualization
影响因子：
--
作者：
D. Morozov;G. Weber
通讯作者：
G. Weber
Felix：基于拓扑的宇宙细丝视觉探索框架
影响因子：
5.2
作者：
N. Shivashankar;Pratyush Pranav;V. Natarajan;R. Weygaert;E. G. P. Bos;S. Rieder
通讯作者：
S. Rieder