Local-Global Merge Tree Computation with Local Exchanges

Arnur Nigmetov, Dmitriy Morozov

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review


A merge tree is a topological summary of a real-valued function on a graph.
Merge trees can be used to find stable features in the data, report the
number of connected components above any threshold, or compute other
topological descriptors. A local--global merge tree provides a way of
distributing a merge tree among multiple processors so that queries can be
performed with minimal communication. While this makes them efficient in
massively parallel setting, the only known algorithm for computing a
local--global merge tree involves global reduction.

Motivated by applications in cosmological simulations, we consider a restricted
version of the problem: we compute a local--global tree down to a threshold
fixed by the user. We describe two algorithms for computing such a tree via
only local exchanges between processors. We present a number of experiments
that show the advantage of our method on different simulations.
Original languageEnglish
Title of host publicationProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis
Subtitle of host publicationSC 19
PublisherAssociation of Computing Machinery
Number of pages13
ISBN (Print)978-1-4503-6229-0
Publication statusPublished - 1 Nov 2019
EventSC19: The International Conference for High Performance Computing, Networking, Storage, and Analysis - Colorado Convention Center, Denver, United States
Duration: 17 Nov 201922 Nov 2019


Country/TerritoryUnited States

Cite this