Graph Sketching and Data Streams
Speaker:

Prof. Andrew McGregor

Date: 09/01/2013
University: Univ. of Massachusetts
Room : A56
Time: 1:00pm (coffee: 12:30)
Slides:
Abstract:

Applying random linear projections, a.k.a. "sketching", has become a standard technique when analyzing high-dimensional data sets. The resulting algorithms are embarrassingly parallelizable and suitable for stream processing. However, existing results have largely focused on vector-based problems (e.g., estimating norms and reconstructing sparse signals) and linear-algebraic problems (e.g., regression and low-rank approximation). In this work, we ask whether the richer combinatorial structure of graphs can also be analyzed via small sketches. We present a range of algorithmic results and applications including the first single-pass algorithm for constructing graph sparsifiers of fully-dynamic graph streams (i.e., where edges can be added and deleted in the underlying graph). Based on joint work with Kook Jin Ahn and Sudipto Guha (SODA 12, PODS 12).

MaDgIK 2009-2018