Practical parallel hypergraph algorithms
- 19 February 2020
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM) in Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
Abstract
While there has been significant work on parallel graph processing, there has been very surprisingly little work on high-performance hypergraph processing. This paper presents a collection of efficient parallel algorithms for hypergraph processing, including algorithms for betweenness centrality, maximal independent set, k-core decomposition, hypertrees, hyperpaths, connected components, PageRank, and single-source shortest paths. For these problems, we either provide new parallel algorithms or more efficient implementations than prior work. Furthermore, our algorithms are theoretically-efficient in terms of work and depth. To implement our algorithms, we extend the Ligra graph processing framework to support hypergraphs, and our implementations benefit from graph optimizations including switching between sparse and dense traversals based on the frontier size, edge-aware parallelization, using buckets to prioritize processing of vertices, and compression. Our experiments on a 72-core machine and show that our algorithms obtain excellent parallel speedups, and are significantly faster than algorithms in existing hypergraph processing frameworks.Keywords
Funding Information
- Semiconductor Research Corporation
- Department of Energy (DE-SC0018947)
- Defense Advanced Research Projects Agency (DE-SC0018947)
- National Science Foundation (CCF-1845763)
This publication has 50 references indexed in Scilit:
- Hypergraph imaging: an overviewPattern Recognition, 2002
- A faster algorithm for betweenness centrality*The Journal of Mathematical Sociology, 2001
- Scheduling multithreaded computations by work stealingJournal of the ACM, 1999
- Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplicationIEEE Transactions on Parallel and Distributed Systems, 1999
- The anatomy of a large-scale hypertextual Web search engineComputer Networks and ISDN Systems, 1998
- Hypergraph traversal revisited: Cost measures and dynamic algorithmsPublished by Springer Science and Business Media LLC ,1998
- The complexity of parallel searchJournal of Computer and System Sciences, 1988
- An O(logn) parallel connectivity algorithmJournal of Algorithms, 1982
- A Set of Measures of Centrality Based on BetweennessSociometry, 1977
- The Parallel Evaluation of General Arithmetic ExpressionsJournal of the ACM, 1974