Sketching High-Dimensional Data

on YouTube ↗01h 10m

" summary

Estimator uses the minimum hashed value of each distinct item (returning 1/X−1), then reduces variance by averaging R independent copies (R ≈ O(1/ε^2)) and improves failure probability with a median-of-means (extra factor ≈ log(1/δ)), all using Flajolet–Martin style order‑statistics. Ideal randomness is replaced by k‑wise independent hash families (e.g. linear/polynomial hashing) storable in O(log n) bits. A practical implementation stores up to K=Θ(1/ε^2) samples per level and achieves roughly O(1/ε^2 log^2 n) bits; matching Ω(1/ε^2) and Ω(log n) lower bounds are known.

AI-written summary · about

" chapters (11)

1. 0:00Start
2. 1:12What Is Sketching
3. 5:57Offline Computation
4. 10:28Optimal Bound
5. 15:20The Distinct Elements Problem
6. 17:29Idealized Algorithm
7. 26:58Flagellae Martin Algorithm
8. 40:03Pseudo Randomness
9. 45:14Polynomial Hashing
10. 47:57Non-Idealized Algorithm
11. 1:02:32What Is Turn Style

" related talks

• 01h 24mStreaming, Sketching and Sufficient Statistics IGraham Cormode · Big Data Boot Camp 2013
• 41mIntegrating Functions via Distance Sensitive HashingMoses Charikar · Real-Time Decision Making 2018
• 35mSampling for Subset Selection and ApplicationsAmit Deshpande · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 26mUsing Random Projections to Make Sense of High-Dimensional ...Stefan Savev · Berlin Buzzwords 2015
• 48mRandomized Numerical Linear AlgebraPetros Drineas · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 01h 26mStreaming, Sketching and Sufficient Statistics IIGraham Cormode · Big Data Boot Camp 2013
• 01h 03mSketching as a Tool for Numerical Linear AlgebraDavid P. Woodruff · Fast Algorithms via Spectral Methods 2014
• 01h 04mSampling Big Ideas in Sublinear AlgorithmsEdith Cohen · Sublinear Algorithms Boot Camp 2024