High on Cardinality, Low on Memory
summary
Four concrete tools and what they actually buy: plain bitsets for true/false arrays, Roaring using RLE to compress sparse bitmaps, Bloom filters are probabilistic with tunable false positive to test membership, and 1.5 kilobytes HyperLogLog to estimate uniques. Claim: per-article interaction sets drop from megabytes to 2 kilobytes per article (approximate) while remaining mergeable across shards. Result: massive memory and latency savings at the cost of controllable approximation; Bloom gives definite negatives, HLL and Bloom trade exactness for tiny, fast summaries.
AI-written summary · about
chapters (9)
- 0:00Memory-efficient data structures
- 1:24Storing booleans in bits
- 4:57Bitmap limitations
- 6:45Compressing sparse bitmaps
- 7:26Bloom filters
- 13:48HyperLogLog for distinct counts
- 20:34Practical applications
- 22:22Why these structures matter
- 24:11Further learning
related talks
01h 00mHyper Speed: When Big Data Blooms
10mDon’t forget to sketch! Running with large datasets
20mAlternative Data Structures in Ruby
41mProbabilistic Data Structures
37mWhen Probably is Good Enough
26mNo, Maybe and Close Enough! Probabilistic Data Structures with Python and Redis
01h 00mCount-min Sketch to Infinity
26mNo, Maybe and Close Enough: Using Probabilistic Data Structures in Python