An Overview on Data Streams Algorithms
summary
Twenty years of graph-streaming results compress into concrete primitives and bounds: L0 sampling via linear sketches lets one pick a uniform live edge with polylog(n) space; the semi-streaming regime uses O~(n) space. Unweighted matching resists any one-pass better-than-2 approximation; weighted matching reaches 2+ε in one pass and 1+ε with O(log n) passes. Dynamic connectivity and cut/spectral sparsifiers arise from signed incidence sketches (players send O(log^3 n) bits each) and repeated sketch subtraction; SNAPE node sampling and low-arboricity degree-weighting give exact or constant-factor matching estimates.
AI-written summary · about
chapters (12)
- 0:00Graph streaming algorithms intro
- 2:00Graph streaming models
- 7:02Linear sketches applications
- 9:09L0 sampling fundamentals
- 15:50Matching challenges in streams
- 20:32Weighted matching progress
- 36:21Insert-delete matching cases
- 44:16Connectivity in graph streams
- 59:28Emulating with sketches
- 1:05:20Independent set and coloring
- 1:15:41Open problems and future
- 1:17:10Q&A
related talks
55mTheory of Data Streams
32mStreaming Algorithms for Matchings in Low Arboricity Graphs
01h 26mStreaming, Sketching and Sufficient Statistics II
01h 04mNew Algorithms for Heavy Hitters in Data Streams
01h 24mStreaming, Sketching and Sufficient Statistics I
19mGraphs as Streams: Rethinking Graph Processing in ... #bbuzz
48mHomomorphic Sketches: Shrinking Big Data without Sacrificing Structure
24mSketching Algorithms: Making Sense of Big Data in a Single Stroke