Universal Sketches
summary
Claim: a single compact sketch approximates an entire family of functions (sums g(v_i), many symmetric norms) rather than one per query. Construction uses a collection of F2 heavy-hitter sketches on subsampled levels (depth ~ log m), CountSketch/AMS-style tools and stable projections for Lp cases. Space scales with a geometric complexity parameter (MMC), roughly space ~ MMC^2 (up to logs), and experiments in software‑defined networking with megabyte device memory and constant‑time updates beat uniform NetFlow sampling.
AI-written summary · about
chapters (19)
- 0:00Intro
- 0:55Outline
- 1:40Streaming Model
- 2:41Sketches
- 3:50Universal Sketches
- 8:16Networks
- 12:26Limitations
- 13:38Network Monitoring
- 16:04Experiments
- 16:28Functions
- 18:15Single Sketch
- 20:37Universal Sketch
- 21:44Symmetric Norm
- 22:50Not every norm is symmetric
- 23:14Explanation
- 29:36Observations
- 33:02Conclusion
- 33:30Shiba Inu
- 37:21Set Systems
related talks
01h 24mStreaming, Sketching and Sufficient Statistics I
01h 26mStreaming, Sketching and Sufficient Statistics II
01h 04mSketching and Randomized Linear Algebra
01h 03mSketching as a Tool for Numerical Linear Algebra
01h 10mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch II
59mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch I
01h 06mData Streams I
53mSketching and Projecting