In this talk, I will give an overview of recent work on parallel dynamic graph algorithms and the closely related graph-streaming setting where a continuous stream of graph updates is mixed with graph queries. In particular, I will focus on (1) Aspen, a a graph-streaming framework that extends the interface of Ligra with operations for updating graphs and (2) the CPAM framework, which enables faster and more space-efficient graph streaming systems with better theoretical guarantees using a new parallel block-based purely-functional data structure. I will end by describing ongoing work on using Aspen to support new applications, and some problems at the interface of algorithm-engineering and theory in this area.
Laxman Dhulipala is an Assistant Professor in the Department of Computer Science at the University of Maryland, College Park. He is also a visiting faculty researcher at Google Research where he works on the Graph Mining team. Previously, he was a postdoc at MIT working with Julian Shun. He obtained his Ph.D. from Carnegie Mellon University, where he was advised by Guy Blelloch. His current research interests are on parallel clustering (graphs and spatial data), and efficient parallel algorithms and systems for static, streaming, and dynamic graphs.