Too Big To Store: Two Decades of Graph Streaming
Many of today's graphs (social networks, web graphs, communication and transaction networks) are too large to store, let alone process, using traditional means. Graph streaming offers a simple model for such settings: the edges of a graph arrive one by one, and an algorithm must process them on the fly using memory much smaller than the input.
Over the past twenty years, this model has become a rich meeting point for algorithms, complexity theory, optimization, and combinatorics. In this talk, I will give an overview of the area: what can and cannot be done in this model and why, and along the way showcase some illustrative examples.
The talk is self-contained and assumes no background in streaming algorithms.
Date
Location
Pittsburgh 4114
