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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Amdahl, G.M.: Validity of the single processor approach to achieving large scale computing capabilities. In: Proceedings of the 18–20 April 1967, Spring Joint Computer Conference, pp. 483–485. ACM (1967)
Bauer, U., Kerber, M., Reininghaus, J., Wagner, H.: Phat-persistent homology algorithms toolbox. J. Symb. Comput. 78, 76–90 (2017)
Beineke, L.W., Wilson, R.J.: Topics in Algebraic Graph Theory, vol. 102. Cambridge University Press, Cambridge (2004)
Boissonnat, J.-D., Dey, T.K., Maria, C.: The compressed annotation matrix: an efficient data structure for computing persistent cohomology. Algorithmica 73(3), 607–619 (2015)
Caliński, T., Harabasz, J.: A dendrite method for cluster analysis. Commun. Stat.-Theory Methods 3(1), 1–27 (1974)
Carlsson, E., Carlsson, G., De Silva, V.: An algebraic topological method for feature identification. Int. J. Comput. Geom. Appl. 16(04), 291–314 (2006)
Carlsson, G.: Topology and data. Bull. Am. Math. Soc. 46(2), 255–308 (2009)
Carlsson, G., Ishkhanov, T., De Silva, V., Zomorodian, A.: On the local behavior of spaces of natural images. Int. J. Comput. Vision 76(1), 1–12 (2008)
Carlsson, G., Mémoli, F.: Persistent clustering and a theorem of j. Kleinberg. arXiv preprint arXiv:0808.2241, 2008
Carlsson, G., Zomorodian, A.: The theory of multidimensional persistence. Discrete Comput. Geom. 42(1), 71–93 (2009)
Carlsson, G., Zomorodian, A., Collins, A., Guibas, L.J.: Persistence barcodes for shapes. Int. J. Shape Model. 11(02), 149–187 (2005)
Carrière, M., Oudot, S.: Structure and stability of the 1-dimensional mapper. arXiv preprint arXiv:1511.05823 (2015)
Chen, C., Kerber, M.: Persistent homology computation with a twist. In: Proceedings 27th European Workshop on Computational Geometry, vol. 11 (2011)
Collins, A., Zomorodian, A., Carlsson, G., Guibas, L.J.: A barcode shape descriptor for curve point cloud data. Comput. Graph. 28(6), 881–894 (2004)
Dey, T.K., Mémoli, F., Wang, Y.: Multiscale mapper: topological summarization via codomain covers. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 997–1013. Society for Industrial and Applied Mathematics (2016)
Dey, T.K., Memoli, F., Wang, Y.: Topological analysis of nerves, reeb spaces, mappers, and multiscale mappers. arXiv preprint arXiv:1703.07387 (2017)
Edelsbrunner, H., Letscher, D., Zomorodian, A.: Topological persistence and simplification. In: Proceedings of 41st Annual Symposium on Foundations of Computer Science, pp. 454–463. IEEE (2000)
Emmett, K., Schweinhart, B., Rabadan, R.: Multiscale topology of chromatin folding. In: Proceedings of the 9th EAI International Conference on Bio-inspired Information and Communications Technologies (formerly BIONETICS), pp. 177–180. ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering) (2016)
Ghrist, R.: Barcodes: the persistent topology of data. Bull. Am. Math. Soc. 45(1), 61–75 (2008)
Gidea, M.: Topology data analysis of critical transitions in financial networks (2017)
Gueunet, C., Fortin, P., Jomier, J., Tierny, J.: Task-based augmented merge trees with fibonacci heaps. In: IEEE Symposium on Large Data Analysis and Visualization (2017)
Günther, D., Reininghaus, J., Wagner, H., Hotz, I.: Efficient computation of 3D morse-smale complexes and persistent homology using discrete morse theory. Vis. Comput. 28(10), 959–969 (2012)
Gyulassy, A., Pascucci, V., Peterka, T., Ross, R.: The parallel computation of morse-smale complexes. In: 2012 IEEE 26th International Parallel & Distributed Processing Symposium (IPDPS), pp. 484–495. IEEE (2012)
Hajij, M., Rosen, P.: An efficient data retrieval parallel reeb graph algorithm. arXiv preprint arXiv:1810.08310 (2018)
Hiraoka, Y., Nakamura, T., Hirata, A., Escolar, E.G., Matsue, K., Nishiura, Y.: Hierarchical structures of amorphous solids characterized by persistent homology. Proc. Natl. Acad. Sci. 113(26), 7035–7040 (2016)
Lewis, R.H., Zomorodian, A.: Multicore homology via mayer vietoris. arXiv preprint arXiv:1407.2275 (2014)
Lipsky, D., Skraba, P., Vejdemo-Johansson, M.: A spectral sequence for parallelized persistence. arXiv preprint arXiv:1112.1245 (2011)
Lum, P.Y., Singh, G., Lehman, A., Ishkanov, T., Vejdemo-Johansson, M., Alagappan, M., Carlsson, J., Carlsson, G.: Extracting insights from the shape of complex data using topology. Sci. Rep. 3, 1236 (2013)
Morozov, D., Weber, G.: Distributed merge trees. In: ACM SIGPLAN Notices, vol. 48, pp. 93–102. ACM (2013)
Morozov, D., Weber, G.H.: Distributed contour trees (2012)
Müllner, D., Babu, A.: Python mapper: an open-source toolchain for data exploration, analysis, and visualization (2013). http://math.stanford.edu/muellner/mapper
Munch, E., Wang, B.: Convergence between categorical representations of reeb space and mapper. arXiv preprint arXiv:1512.04108 (2015)
Munkres, J.R.: Elements of Algebraic Topology, vol. 2. Addison-Wesley, Menlo Park (1984)
Nicolau, M., Levine, A.J., Carlsson, G.: Topology based data analysis identifies a subgroup of breast cancers with a unique mutational profile and excellent survival. Proc. Natl. Acad. Sci. 108(17), 7265–7270 (2011)
Otter, N., Porter, M.A., Tillmann, U., Grindrod, P., Harrington, H.A.: A roadmap for the computation of persistent homology. EPJ Data Sci. 6(1), 17 (2017)
Pascucci, V., Cole-McLaughlin, K.: Parallel computation of the topology of level sets. Algorithmica 38(1), 249–268 (2004)
Robins, V.: Towards computing homology from finite approximations. Topol. Proc. 24, 503–532 (1999)
Robles, A., Hajij, M., Rosen, P.: The shape of an image: a study of mapper on images. In: VISAPP 2018 (2018, to appear)
Rosen, P., Tu, J., Piegl, L.: A hybrid solution to calculating augmented join trees of 2D scalar fields in parallel. In: CAD Conference and Exhibition (2017, accepted)
Shivashankar, N., Senthilnathan, M., Natarajan, V.: Parallel computation of 2D Morse-Smale complexes. IEEE Trans. Vis. Comput. Graph. 18(10), 1757–1770 (2012)
Singh, G., Mémoli, F., Carlsson, G.E.: Topological methods for the analysis of high dimensional data sets and 3D object recognition. In: SPBG, pp. 91–100 (2007)
Snášel, V., Nowaková, J., Xhafa, F., Barolli, L.: Geometrical and topological approaches to big data. Future Gener. Comput. Syst. 67, 286–296 (2017)
Sumner, R.W., Popović, J.: Deformation transfer for triangle meshes. ACM Trans. Graph. (TOG) 23(3), 399–405 (2004)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Hajij, M., Assiri, B., Rosen, P. (2021). Parallel Mapper. In: Arai, K., Kapoor, S., Bhatia, R. (eds) Proceedings of the Future Technologies Conference (FTC) 2020, Volume 2 . FTC 2020. Advances in Intelligent Systems and Computing, vol 1289. Springer, Cham. https://doi.org/10.1007/978-3-030-63089-8_47
Download citation
DOI: https://doi.org/10.1007/978-3-030-63089-8_47
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-63088-1
Online ISBN: 978-3-030-63089-8
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)