Sketching Merge Trees for Scientific Data Visualization

Merge trees are a type of topological descriptors that record the connectivity among the sublevel sets of scalar fields. They are among the most widely used topological tools in visualization. In this paper, we are interested in sketching a set of merge trees. That is, given a large set T of merge trees, we would like to find a much smaller basis set S such that each tree in T can be approximately reconstructed from a linear combination of merge trees in S. A set of high-dimensional vectors can be sketched via matrix sketching techniques such as principal component analysis and column subset selection. However, up until now, topological descriptors such as merge trees have not been known to be sketchable. We develop a framework for sketching a set of merge trees that combines the Gromov-Wasserstein probabilistic matching with techniques from matrix sketching. We demonstrate the applications of our framework in sketching merge trees that arise from time-varying scientific simulations. Specifically, our framework obtains a much smaller representation of a large set of merge trees for downstream analysis and visualization. It is shown to be useful in identifying good representatives and outliers with respect to a chosen basis. Finally, our work shows a promising direction of utilizing randomized linear algebra within scientific visualization.