Parallel Mapper

The construction of Mapper has emerged in the last decade as a powerful and effective topological data analysis tool that approximates and generalizes other topological summaries, such as the Reeb graph, the contour tree, split, and joint trees. In this paper we study the parallel analysis of the construction of Mapper. We give a provably correct parallel algorithm to execute Mapper on a multiple processors. Our algorithm relies on a divide and conquer strategy for the codomain cover which gets pulled back to the domain cover. We demonstrate our approach for topological Mapper then we show how it can be applied to the statistical version of Mapper. Furthermore, we discuss the performance results that compare our approach to a reference sequential Mapper implementation. Finally, we report the performance experiments that demonstrate the efficiency of our method. To the best of our knowledge this is the first algorithm that addresses the computation of Mapper in parallel.

Mustafa Hajij, Basem Assiri, and Paul Rosen. Parallel Mapper. Proceedings of the Future Technologies Conference, 2020.

@inproceedings{hajij2020parallel,
  title = {Parallel Mapper},
  author = {Hajij, Mustafa and Assiri, Basem and Rosen, Paul},
  booktitle = {Proceedings of the Future Technologies Conference},
  pages = {717--731},
  year = {2020},
  abstract = {The construction of Mapper has emerged in the last decade as a powerful and
    effective topological data analysis tool that approximates and generalizes other
    topological summaries, such as the Reeb graph, the contour tree, split, and joint trees.
    In this paper we study the parallel analysis of the construction of Mapper. We give a
    provably correct parallel algorithm to execute Mapper on a multiple processors. Our
    algorithm relies on a divide and conquer strategy for the codomain cover which gets
    pulled back to the domain cover. We demonstrate our approach for topological Mapper then
    we show how it can be applied to the statistical version of Mapper. Furthermore, we
    discuss the performance results that compare our approach to a reference sequential
    Mapper implementation. Finally, we report the performance experiments that demonstrate
    the efficiency of our method. To the best of our knowledge this is the first algorithm
    that addresses the computation of Mapper in parallel.}
}