You are invited to attend Evan West's public PhD Proposal.  Details below.

Everyone is welcome!

Who: Evan West

When: Friday, December 6 at 11:00 AM

Where: NCS 115

Title: Useful Graph Semi-Streaming: Expanding the Scope of Dynamic Graph Processing with Algorithms Theory and Software Engineering

Abstract: Systems for graph-processing (computing some property of a graph) are commonly designed for computing on sparse static graphs. Graph-processing becomes more challenging when the graph is large or if it is dynamic, that is, the graph changes over time subject to a stream of edge insertions and deletions. Graphs have notoriously low data locality and as such, to process a large dynamic graph requires us to have enough RAM to store the entire graph. This approach is acceptable for sparse graphs, but for dense graphs (where the size of the graph increases super-linearly with respect to the number of vertices) this is a prohibitive limitation for graph-processing.

In this dissertation, we present high-performance graph-processing systems for computing connected components on dynamic graphs. These systems leverage new linear sketching data-structures, new graph sketching algorithms, and systems engineering to enable performant computation on large dense graphs. On a single machine, our graph-processing system reaches 80 million edge updates per second and performs queries in less than a second. With a distributed cluster of workers, our system obtains an ingestion rate of over 300 million updates per second.

Additionally, we design new graph sketching algorithms for k-edge connectivity and approximate minimum cut that reduce the space complexity by a factor O(log V) (where V is the number of graph vertices) when compared to the state of the art semi-streaming algorithms. These improvements allow for practical computation of these properties on large dense graph streams.