Skip to main content
back to events

Graph Sketching and Data Streams

Speaker:Prof. Andrew McGregor


University:Univ. of Massachusetts

Room :A56

Time:1:00pm (coffee: 12:30)



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).

Related websites
No related websites
Related organizations
No related organizations