Write a Blog >>
Tue 25 Feb 2020 14:00 - 14:25 - Graph (Mediterranean Ballroom) Chair(s): Jiajia Li

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 computing hypertrees, hyperpaths, betweenness centrality, maximal independent sets, $k$-core decomposition, 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.

Tue 25 Feb
Times are displayed in time zone: Tijuana, Baja California change

14:00 - 15:15: Graph (Mediterranean Ballroom)Main Conference
Chair(s): Jiajia LiPacific Northwest National Laboratory
14:00 - 14:25
Practical Parallel Hypergraph Algorithms
Main Conference
14:25 - 14:50
A Supernodal All-Pairs Shortest Path Algorithm
Main Conference
piyush kumar saoOak Ridge National Lab, Ramki KannanOak Ridge National Laboratory, Prasun GeraGeorgia Institute of Technology, Rich VuducGeorgia Institute of Technology
14:50 - 15:15
Increasing the Parallelism of Graph Coloring via Shortcutting
Main Conference
Ghadeer AlabandiTexas State University, Evan PowersTexas State University, Martin BurtscherTexas State University