Data Streams II
summary
CountSketch is used to turn unbiased dot‑product estimators into a practical CountSketch with B≈10·K buckets and hash repetitions T=Θ(log n): each bucket stores a signed counter whose variance equals the sum of squared frequencies of colliding items, and the median of row estimates yields point queries accurate up to about sqrt((‖tail‖2^2)/B). For graphs, edges are sampled proportional to effective resistance estimated via sketching B·(approximate potentials): maintain CountSketches of geometrically subsampled edge lists, recover edges with resistance ≥1/log n, and reweight survivors to build a spectral sparsifier.
AI-written summary · about
chapters (9)
- 0:00Introduction to count sketch
- 1:07Heavy hitters and estimators
- 7:00Count sketch analysis
- 14:20L2 heavy hitters
- 24:33Spectral graph sparsification
- 30:44Streaming graph sparsification
- 37:12Effective resistance estimation
- 51:05Geometric sampling algorithm
- 57:36Summary and open problems
related talks
27mSampling Algorithms to Count Frequent Patterns in Graphs
34mError Estimation for Randomized Numerical Linear Algebra: Bootstrap Methods
29mApplying Randomized Methods for Zonotope Enumeration and...
32mAdventures with Randomized Algebra for Extreme-Scale Signal Processing
01h 03mSimons Institute Live Stream
36mUnbiased Estimates for Linear Regression via Volume Sampling
48mTesting Positive Semidefiniteness and Eigenvalue Approximation
24mHighlights from Current Programs part 2: