MASTIFF: structure-aware minimum spanning tree/forest

Mohsen Koohi Esfahani, Peter Kilpatrick, Hans Vandierendonck

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)
221 Downloads (Pure)

Abstract

The Minimum Spanning Forest (MSF) problem finds usage in many different applications. While theoretical analysis shows that linear-time solutions exist, in practice, parallel MSF algorithms remain computationally demanding due to the continuously increasing size of data sets.

In this paper, we study the MSF algorithm from the perspective of graph structure and investigate the implications of the power-law degree distribution of real-world graphs on this algorithm.

We introduce the MASTIFF algorithm as a structure-aware MSF algorithm that optimizes work efficiency by (1) dynamically tracking the largest forest component of each graph component and exempting them from processing, and (2) by avoiding topology-related operations such as relabeling and merging neighbour lists.

The evaluations on 2 different processor architectures with up to 128 cores and on graphs of up to 124 billion edges, shows that Mastiff is 3.4--5.9X faster than previous works.

Original languageEnglish
Title of host publicationProceedings of the 36th ACM International Conference on Supercomputing, ICS 2022
PublisherAssociation for Computing Machinery
Number of pages13
ISBN (Electronic)9781450392815
DOIs
Publication statusPublished - 28 Jun 2022
Event36th ACM International Conference on Supercomputing - virtual, online
Duration: 28 Jun 202230 Jun 2022

Publication series

Name ACM International Conference on Supercomputing: Proceedings
PublisherACM

Conference

Conference36th ACM International Conference on Supercomputing
Abbreviated titleICS'22
Cityvirtual, online
Period28/06/202230/06/2022

Keywords

  • Graph Algorithms
  • High Performance Computing
  • Real-World Graphs
  • Minimum Spanning Tree
  • Minimum Spanning Forest

Fingerprint

Dive into the research topics of 'MASTIFF: structure-aware minimum spanning tree/forest'. Together they form a unique fingerprint.

Cite this