Sketching Merge Trees. (arXiv:2101.03196v1 [cs.CG])

Merge trees are a type of topological descriptors that record the
connectivity among the sublevel sets of scalar fields. In this paper, we are
interested in sketching a set of merge trees. That is, given a set T of merge
trees, we would like to find a 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 framework of Chowdhury and Needham with
techniques from matrix sketching. We demonstrate the applications of our
framework in sketching merge trees that arise from data ensembles in scientific
simulations.