Evaluation of connected-component labeling algorithms for distributed-memory systems

J. Iverson, C. Kamath, G. Karypis

Research output: Contribution to journalArticlepeer-review

19 Scopus citations

Abstract

Connected component labeling is a key step in a wide-range of applications, such as community detection in social networks and coherent structure identification in massively-parallel scientific simulations. There have been several distributed-memory connected component algorithms described in literature; however, little has been done regarding their scalability analysis. Theoretical and experimental results are presented for five algorithms: three that are direct implementations of previous approaches, one that is an implementation of a previous approach that is optimized to reduce communication, and one that is a novel approach based on graph contraction. Under weak scaling and for certain classes of graphs, the graph contraction algorithm scales consistently better than the four other algorithms. Furthermore, it uses significantly less memory than two of the alternative methods and is of the same order in terms of memory as the other two.

Original languageEnglish (US)
Pages (from-to)53-68
Number of pages16
JournalParallel Computing
Volume44
DOIs
StatePublished - May 2015

Bibliographical note

Funding Information:
This work was supported in part by NSF – United States ( IIS-0905220 , OCI-1048018 , and IOS-0820730 ) and by the DOE Grant USDOE/ DE-SC0005013 (as part of the Exa-DM project, funded by Dr. Lucy Nowell, program manager, ASCR), and the Digital Technology Center at the University of Minnesota. Access to research and computing facilities was provided by the Digital Technology Center and the Minnesota Supercomputing Institute.

Publisher Copyright:
© 2015 Published by Elsevier B.V.

Keywords

  • Connected component
  • Distributed-memory
  • Scalability

Fingerprint

Dive into the research topics of 'Evaluation of connected-component labeling algorithms for distributed-memory systems'. Together they form a unique fingerprint.

Cite this