Lyu Weiran, Sridharamurthy Raghavendra, Phillips Jeff M, Wang Bei
IEEE Trans Vis Comput Graph. 2025 Jan;31(1):141-151. doi: 10.1109/TVCG.2024.3456383. Epub 2024 Nov 25.
Scalar field comparison is a fundamental task in scientific visualization. In topological data analysis, we compare topological descriptors of scalar fields-such as persistence diagrams and merge trees-because they provide succinct and robust abstract representations. Several similarity measures for topological descriptors seem to be both asymptotically and practically efficient with polynomial time algorithms, but they do not scale well when handling large-scale, time-varying scientific data and ensembles. In this paper, we propose a new framework to facilitate the comparative analysis of merge trees, inspired by tools from locality sensitive hashing (LSH). LSH hashes similar objects into the same hash buckets with high probability. We propose two new similarity measures for merge trees that can be computed via LSH, using new extensions to Recursive MinHash and subpath signature, respectively. Our similarity measures are extremely efficient to compute and closely resemble the results of existing measures such as merge tree edit distance or geometric interleaving distance. Our experiments demonstrate the utility of our LSH framework in applications such as shape matching, clustering, key event detection, and ensemble summarization.
标量场比较是科学可视化中的一项基本任务。在拓扑数据分析中，我们比较标量场的拓扑描述符，如持久图和合并树，因为它们提供了简洁且稳健的抽象表示。对于拓扑描述符的几种相似性度量似乎在渐近和实际应用中都能通过多项式时间算法实现高效计算，但在处理大规模、时变的科学数据和数据集时，它们的扩展性不佳。在本文中，我们受局部敏感哈希（Locality Sensitive Hashing，LSH）工具的启发，提出了一个新的框架来促进合并树的比较分析。LSH 以高概率将相似对象哈希到同一个哈希桶中。我们分别使用递归最小哈希（Recursive MinHash）和子路径签名的新扩展，为合并树提出了两种可以通过 LSH 计算的新相似性度量。我们的相似性度量计算效率极高，并且与现有度量（如合并树编辑距离或几何交织距离）的结果非常相似。我们的实验证明了我们的 LSH 框架在形状匹配、聚类、关键事件检测和数据集汇总等应用中的实用性。
