Supervision : Julien TIERNY

Co-supervision : FORTIN Pierre, JOMIER Julien

High Performance Level-set based Topological Data Analysis

Topological Data Analysis requires efficient algorithms to deal with the continuously increasing size and level of details of data sets. In this manuscript, we focus on three fundamental topological abstractions based on level sets: merge trees, contour trees and Reeb graphs. We propose three new efficient parallel algorithms for the computation of these abstractions on multi-core shared memory workstations. The first algorithm developed in the context of this thesis is based on multi-thread parallelism for the contour tree computation. A second algorithm revisits the reference sequential algorithm to compute this abstraction and is based on local propagations expressible as parallel tasks. This new algorithm is in practice twice faster in sequential than the reference algorithm designed in 2000 and offers one order of magnitude speedups in parallel. A last algorithm also relying on task-based local propagations is presented, computing a more generic abstraction: the Reeb graph. Contrary to concurrent approaches, these methods provide the augmented version of these structures, hence enabling the full extend of level-set based analysis. Algorithms presented in this manuscript result today in the fastest implementations available to compute these abstractions. This work has been integrated into the open-source platform: the Topology Toolkit (TTK).

2016-2023 Publications

• 2023
  • M. Flatken, A. Podobas, R. Fellegara, A. Basermann, J. Holke, D. Knapp, M. Kontak, Ch. Krullikowski, M. Nolde, N. Brown, R. Nash, G. Gibb, E. Belikov, S. Chien, S. Markidis, P. Guillou, J. Tierny, J. Vidal, Ch. Gueunet, J. Günther, M. Pawlowski, P. Poletti, G. Guzzetta, M. Manica, A. Zardini, J.‑P. Chaboureau, M. Mendes, A. Cardil, S. Monedero, J. Ramirez, A. Gerndt : “VESTEC: Visual Exploration and Sampling Toolkit for Extreme Computing: Urgent Decision Making Meets HPC: Experiences and Future Challenges”, IEEE Access, vol. 11, pp. 87805-87834, (IEEE) (2023)
• 2022
  • Ch. Garth, Ch. Gueunet, P. Guillou, F. Iuricich, J. Levine, J. Lukasczyk, M. Pont, J. Tierny, J. Vidal, B. Wang, F. Wetzels : “Topological Analysis of Ensemble Scalar Data with TTK, A Sequel”, IEEE VIS Tutorials, Oklahoma City, United States (2022)
• 2021
  • N. Brown, R. Nash, P. Poletti, G. Guzzetta, M. Manica, A. Zardini, M. Flatken, J. Vidal, Ch. Gueunet, E. Belikov, J. Tierny, A. Podobas, W. Der Chien, S. Markidis, A. Gerndt : “Utilising urgent computing to tackle the spread of mosquito-borne diseases”, IEEE/ACM HPC for Urgent Decision Making (UrgentHPC) 2021, St. Louis, United States, pp. 36-44, (IEEE) (2021)
  • Ch. Garth, Ch. Gueunet, P. Guillou, L. Hofmann, J. Levine, J. Lukasczyk, J. Tierny, J. Vidal, B. Wang, F. Wetzels : “Topological Analysis of Ensemble Scalar Data with TTK”, IEEE VIS Tutorials, IEEE VIS Tutorials, New Orleans, United States (2021)
• 2020
  • M. Falk, Ch. Garth, Ch. Gueunet, P. Guillou, A. Gyulassy, L. Hofmann, Ch. Kappe, J. Levine, J. Lukasczyk, J. Tierny, J. Vidal : “Topological Data Analysis Made Easy with the Topology ToolKit, What is New?”, IEEE VIS Tutorials, Salt Lake City, United States (2020)
• 2019
  • Ch. Gueunet : “Calcul Haute Performance pour l’Analyse Topologique de Données par Ensembles de Niveaux”, thesis, phd defence 02/15/2019, supervision Tierny, Julien, co-supervision : Fortin, Pierre, Jomier, Julien (2019)
  • M. Falk, Ch. Garth, Ch. Gueunet, J. Levine, J. Lukasczyk, J. Tierny, J. Vidal : “Topological Data Analysis Made Easy with the Topology ToolKit, A Sequel”, IEEE VIS Tutorials, Vancouver, Canada (2019)
  • T. Bin Masood, J. Budin, M. Falk, G. Favelier, Ch. Garth, Ch. Gueunet, P. Guillou, L. Hofmann, P. Hristov, A. Kamakshidasan, Ch. Kappe, P. Klacansky, P. Laurin, J. Levine, J. Lukasczyk, D. Sakurai, M. Soler, P. Steneteg, J. Tierny, W. Usher, J. Vidal, M. Wozniak : “An Overview of the Topology ToolKit”, TopoInVis 2019 - Topological Methods in Data Analysis and Visualization, Nykoping, Sweden (2019)
  • Ch. Gueunet, P. Fortin, J. Jomier, J. Tierny : “Task-based Augmented Reeb Graphs with Dynamic ST-Trees”, Eurographics Symposium on Parallel Graphics and Visualization, Porto, Portugal (2019)
  • Ch. Gueunet, P. Fortin, J. Jomier, J. Tierny : “Task-based Augmented Contour Trees with Fibonacci Heaps”, IEEE Transactions on Parallel and Distributed Systems, vol. 30 (8), pp. 1889-1905, (Institute of Electrical and Electronics Engineers) (2019)
• 2018
  • G. Favelier, Ch. Gueunet, A. Gyulassy, J. Kitware, J. Levine, J. Lukasczyk, D. Sakurai, M. Soler, J. Tierny, W. Usher, Q. Wu : “Topological Data Analysis Made Easy with the Topology ToolKit”, IEEE VIS Tutorials, Berlin, Germany (2018)
• 2017
  • Ch. Gueunet, P. Fortin, J. Jomier, J. Tierny : “Task-based Augmented Merge Trees with Fibonacci Heaps”, IEEE Symposium on Large Data Analysis and Visualization 2017, Phoenix, United States (2017)
  • J. Tierny, G. Favelier, J. Levine, Ch. Gueunet, M. Michaux : “The Topology ToolKit”, IEEE Transactions on Visualization and Computer Graphics, (Institute of Electrical and Electronics Engineers) (2017)
  • J. Lukasczyk, G. Aldrich, M. Steptoe, G. Favelier, Ch. Gueunet, J. Tierny, R. Maciejewski, B. Hamann, H. Leitte : “Viscous Fingering: A Topological Visual Analytic Approach”, Physical Modeling for Virtual Manufacturing Systems and Processes, Speyer, Germany (2017)
• 2016
  • Ch. Gueunet, P. Fortin, J. Jomier, J. Tierny : “Contour Forests: Fast Multi-threaded Augmented Contour Trees”, IEEE Symposium on Large Data Analysis and Visualization, Baltimore, United States (2016)
  • G. Favelier, Ch. Gueunet, J. Tierny : “Visualizing Ensembles of Viscous Fingers”, IEEE Scientific Visualization Contest, Baltimore, United States (2016)