Vertex and Hyperedge Connectivity in Dynamic Graph Streams
Sudipto Guha, Andrew McGregor, David Tench · 2015
A growing body of work addresses the challenge of processing dynamic graph streams: a graph is defined by a sequence of edge insertions and deletions and the goal is to construct synopses and compute properties of the graph while using only limited memory. Linear sketches have proved to be a powerful technique in this model and can also be used to minimize communication in distributed graph processing.