Don’t forget to sketch! Running with large datasets
summary
Shows concrete sketches: Bloom Filters that use bit arrays and hashes and a formula giving ~20 bits per item ⇒ ~1 false positive per 10,000 lookups (10M malicious URLs compress to ~24 MB vs >1 GB of raw strings), Count-min Sketches that keep multiple counter rows and return the min to give one-sided overestimates that are accurate for heavy hitters, and HyperLogLogs for distinct counts; hand-drawn demos and worked-through numbers replace vague promises.
AI-written summary · about
chapters (9)
- 0:00Intro
- 0:35Sketch definition
- 0:50What is a sketch
- 1:37Bloom Filters
- 4:36False Positive Math
- 5:21False Positive Rate
- 5:55Count Min
- 8:42Final Thoughts
- 9:22Embrace Randomness
related talks
37mWhen Probably is Good Enough
25mHigh on Cardinality, Low on Memory
01h 00mCount-min Sketch to Infinity
01h 00mHyper Speed: When Big Data Blooms
45mMost of the Time It Works Every Time: The Mindset Behind Using Probabilistic Data Structures
43mResizable Sketches
27mImproved Frequency Estimation Algorithms with and without Predictions
20mAlternative Data Structures in Ruby