Laxman Dhulipala

Provably Efficient and Scalable Shared- Memory Graph Algorithms Degree Type: Ph.D. in Computer Science
Advisor(s): Guy Blelloch
Graduated: August 2020

Abstract:

Graph processing is a fundamental tool in many computational disciplines due to the widespread availability of graph data. However, processing large graphs quickly and cost-effectively is a major challenge, and existing approaches capable of processing large graphs have high computational cost,only solve a limited set of problems, and possess poor theoretical guarantees. Similarly, existing graph processing approaches for dynamic or streaming graphs employ ad-hoc algorithms with unknown theoretical costs and suboptimal performance. This thesis argues that shared-memory algorithms can serve as the foundation for a graph processing toolkit for static and evolving graphs that is cost-effective, has strong theoretical guarantees, and achieves state-of-the-art performance.

The first part of this thesis studies static graph processing. We design a rich interface for parallel graph processing which extends the Ligrainter face with provably efficient primitives. Using the interface, we design provably-efficient shared-memory implementations of over 20 fundamental graph problems. Our implementations, which we have made publicly available as part of the GraphBased Benchmark Suite, solve these problems on the largest publicly available graph, the WebDataCommons hyperlink graph, with over 200 billion edges, in a matter of seconds to minutes using a commodity multicore machine. We also adapt our algorithms for graphs stored in non-volatile memory, thereby extending our results to graphs larger than main memory. Compared to existing graph processing results, our results apply to a much broader set of problems, use orders of magnitude fewer resources,and in many cases run an order of magnitude faster.

The second part of this thesis studies graph processing in the batch-dynamic model, which generalizes the classic dynamic algorithms model by allowing algorithms to ingest batches of updates. We design work-efficient parallel batch-dynamic algorithms with polylogarithmic depth for the dynamic trees and dynamic connectivity problems. We show that shared-memory parallel batch-dynamic algorithms can achieve strong speedups and outperform the fastest sequential dynamic algorithm baselines.

The final part of this thesis studies streaming graph processing. We design a compressed purely-functional tree data structure, called a C-tree, which admits efficient parallel batch updates and enables a dynamic graph representation based on nested trees. Using this representation, we design a serializable graph-streaming system called Aspen that can concurrently apply updates and queries. Compared to existing work, Aspen achieves orders of magnitude higher update rates, while using less memory. We show that Aspen can concurrently update and analyze the WebDataCommons hyperlink graph on a single commodity multicore machine.

Thesis Committee:
Guy C. Blelloch (Chair)
Umut Acar
Phillip B. Gibbons
Vahab Mirrokni (Google Research)
Julian Shun (Massachusetts Institute of Technology)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Keywords:
Parallel algorithms, shared-memory algorithms, parallel graph processing, parallel batch-dynamic algorithms, graph-streaming systems