Efficient Algorithms and Systems for Dynamic and Streaming Graphs

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.