Most of the Time It Works Every Time: The Mindset Behind Using Probabilistic Data Structures
summary
Shows that skip lists use a 50/50 coin flip to promote nodes so searches run in O(log n) with high probability while using about 2n pointers of space; lowering promotion to 1/16 roughly doubles search time. Gives concrete failure odds (e.g., threefold slowdowns are vanishingly rare for millions of items). Demonstrates Bloom filters as tiny pre-checks that yield false positives only and speed up cache/database access in a real backend, and Count‑Min Sketches as fixed‑size counters returning safe upper bounds for frequencies.
AI-written summary · about
chapters (8)
- 0:00Probabilistic data structures
- 4:23Skip lists as prob data structs
- 16:37Practical skip lists with coin flips
- 28:10Skip lists vs tree alternatives
- 31:01Bloom filters for membership
- 36:22Count Min sketch for frequency
- 39:34Summary of prob data structs
- 40:37Q&A
related talks
41mProbabilistic Data Structures
26mNo, Maybe and Close Enough: Using Probabilistic Data Structures in Python
37mWhen Probably is Good Enough
10mDon’t forget to sketch! Running with large datasets
26mNo, Maybe and Close Enough! Probabilistic Data Structures with Python and Redis
01h 00mCount-min Sketch to Infinity
25mHigh on Cardinality, Low on Memory
20mAlternative Data Structures in Ruby