IEEE VIS 2024 Content: Fast Comparative Analysis of Merge Trees Using Locality-Sensitive Hashing

Fast Comparative Analysis of Merge Trees Using Locality-Sensitive Hashing

Weiran Lyu - University of Utah, SALT LAKE CITY, United States

Raghavendra Sridharamurthy - University of Utah, Salt Lake City, United States

Jeff M. Phillips - University of Utah, Salt Lake City, United States

Bei Wang - University of Utah, Salt Lake City, United States

Room: Bayshore I

2024-10-17T14:27:00ZGMT-0600Change your timezone on the schedule page
2024-10-17T14:27:00Z
Exemplar figure, described by caption below
An overview of our pipeline is shown in the representative image. Given a set of scalar fields as input, we first simplify each scalar field using a small persistence threshold to remove noise from the data. We then compute the corresponding merge tree with labeling. These merge trees are subsequently used to generate signatures using either the RMH or subpath signature algorithms. Locality-sensitive hashing (LSH) is employed to divide the signatures into bands and rows. Finally, for empirical comparison, we generate distance matrices by collecting similar pairs from the LSH.
Fast forward
Full Video
Keywords

Merge trees, locality sensitive hashing, comparative analysis, topological data analysis, scientific visualization

Abstract

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.