Data Streams I

on YouTube ↗01h 06m

" summary

Shows that classic linear sketches (distinct‑elements, AMS) are applied to the graph edge‑incidence matrix to handle dynamic edge insertions and deletions, giving a single‑pass algorithm that builds spanning forests via Borůvka‑style rounds (O(log n) rounds, need independent L0 sampler sketches per round) and yields optimal space ≈ n log^3 n bits; also uses L2 (AMS/JL) sketches to produce spectral sparsifiers and defines L0 samplers (recover 1‑sparse via two linear measurements, extend by random subsampling).

AI-written summary · about

" chapters (11)

1. 0:00Introduction
2. 4:46Network Statistics
3. 7:46Classical Approach
4. 28:38Graph Streaming Model
5. 33:53Caching
6. 35:38Edge Incidence Matrix
7. 44:58Summary
8. 47:18Linear Sketch
9. 51:33Connectivity Algorithm
10. 56:23L0 Sampler
11. 56:58Linear Sketches

" related talks

• 01h 26mStreaming, Sketching and Sufficient Statistics IIGraham Cormode · Big Data Boot Camp 2013
• 01h 24mStreaming, Sketching and Sufficient Statistics IGraham Cormode · Big Data Boot Camp 2013
• 39mUniversal SketchesVladimir Braverman · Sublinear Algorithms and Nearest-Neighbor Search
• 01h 04mSketching and Randomized Linear AlgebraDavid P. Woodruff · Sublinear Algorithms Boot Camp 2024
• 01h 03mSketching as a Tool for Numerical Linear AlgebraDavid P. Woodruff · Fast Algorithms via Spectral Methods 2014
• 31mSimple and Deterministic Matrix SketchesEdo Liberty · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 01h 50mData sketching workshopWilliam Benton, Erik Erlandson · DevConf.CZ 2019
• 47mSuccinct Representations and Efficient Algorithms Based on Linear ProgrammingSudipto Guha · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)