- Title: Graph Streams and Sketches
- Authors: Andrew McGregor
Graph Streams and Sketches
This webpage was set up to accompany a tutorial at ICML 2016.
- Part I: Streaming, Sampling, and Sketching Andrew McGregor
- Part II: Space-Efficient Optimization Sudipto Guha
Other General Resources
The following is not an exhaustive list of papers that are relevant to the topic but should include the most relevant and recent papers.
- Vertex and Edge Connectivity and Graph Sparsification
- Single Pass Spectral Sparsification in Dynamic Streams FOCS 2014 (M. Kapralov, Y. T. Lee, C. Musco, C. Musco, A. Sidford)
- Vertex and Hyperedge Connectivity in Dynamic Graph Streams PODS 2015 (S. Guha, A. McGregor, D. Tench)
- Graph Sketches: Sparsfiers, Spanners, and Subgraphs PODS 2012 (K. Ahn, S. Guha, A. McGregor)
- Analyzing Graph Structure via Linear Measurements SODA 2012 (K. Ahn, S. Guha, A. McGregor)
- Spectral Sparsification of Dynamic Graph Streams APPROX 2013 (K. Ahn, S. Guha, A. McGregor)
- Matchings and Vertex Cover
- Kernelization via Sampling with Applications to Dynamic Graph Streams SODA 2016 (R. Chitnis, G. Cormode, H. Esfandiari, M. Hajiaghayi, A. McGregor, M. Monemizadeh, S. Vorotnikova)
- Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem SODA 2016. S. Assadi, S. Khanna, Y. Li.
- Triangle Counting, Frequent Subgraphs, Clustering Coefficients
- Better Algorithms for Counting Triangles in Data Streams PODS 2016 (A. McGregor, S. Vorotnikova, H. Vu)
- Colorful Triangle Counting and a MapReduce Implementation. Rasmus Pagh, Charalampos E. Tsourakakis
- Set Cover
- Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem FOCS 2016. S. Assadi, S. Khanna, Y. Li.
- Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover SODA 2016. A. Chakrabarti, A. Wirth.
- Towards Tight Bounds for the Streaming Set Cover Problem PODS 2016. S. Har-Peled, P. Indyk, S. Mahabadi, A. Vakilian.
- Densest Subgraph
- Correlation Clustering
- Bayesian Networks
- Dynamic Graphs in the Sliding-Window Model ESA 2013 (M. Crouch, A. McGregor, D. Stubbs)