Contour Algorithm for Connectivity

Zhihui Du, Oliver Alvarado Rodriguez, Fuhuan Li, Mohammad Dindoost, David A. Bader

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

Abstract

Finding connected components in a graph is a fundamental problem in graph analysis. In this work, we present a novel minimum-mapping based Contour algorithm to efficiently solve the connectivity problem. We prove that the Contour algorithm with two or higher order operators can identify all connected components of an undirected graph within O (log dmax) iterations, with each iteration involving O(m) work, where dmax represents the largest diameter among all components in the given graph, and m is the total number of edges in the graph. Importantly, each iteration is highly parallelizable, making use of the efficient minimum-mapping operator applied to all edges. To further enhance its practical performance, we optimize the Contour algorithm through asynchronous updates, early convergence checking, eliminating atomic operations, and choosing more efficient mapping operators. Our implementation of the Contour algorithm has been integrated into the open-source framework Arachne. Arachne extends Arkouda for large-scale interactive graph analytics, providing a Python API powered by the high-productivity parallel language Chapel. Experimental results on both real-world and synthetic graphs demonstrate the superior performance of our proposed Contour algorithm compared to state-of-the-art large-scale parallel algorithm FastSV and the fastest shared memory algorithm ConnectIt. On average, Contour achieves a speedup of 7.3x and 1.4x compared to FastSV and ConnectIt, respectively. All code for the Contour algorithm and the Arachne framework is publicly available on GitHub11https://githuh.comJBears-R-Us/arkouda-njit, ensuring transparency and reproducibility of our work.

Original languageEnglish (US)
Title of host publicationProceedings - 2023 IEEE 30th International Conference on High Performance Computing, Data, and Analytics, HiPC 2023
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages66-75
Number of pages10
ISBN (Electronic)9798350383225
DOIs
StatePublished - 2023
Event30th Annual IEEE International Conference on High Performance Computing, Data, and Analytics, HiPC 2023 - Goa, India
Duration: Dec 18 2023Dec 21 2023

Publication series

NameProceedings - 2023 IEEE 30th International Conference on High Performance Computing, Data, and Analytics, HiPC 2023

Conference

Conference30th Annual IEEE International Conference on High Performance Computing, Data, and Analytics, HiPC 2023
Country/TerritoryIndia
CityGoa
Period12/18/2312/21/23

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Computer Networks and Communications
  • Computer Science Applications
  • Hardware and Architecture
  • Information Systems
  • Information Systems and Management

Keywords

  • big data
  • connected components
  • graph analytics
  • parallel algorithm

Fingerprint

Dive into the research topics of 'Contour Algorithm for Connectivity'. Together they form a unique fingerprint.

Cite this