Art of Codeartofcode
Lesson 14 of 15

20. Probabilistic Data Structures

1
The picture to keep in your head
2
20.1 Why is "approximately right, fast and tiny" a good trade?
3
20.2 How does a Bloom filter work?
4
20.3 What is a counting Bloom filter?
5
20.4 How does HyperLogLog count unique visitors?
6
20.5 What is a count-min sketch?
7
20.6 How do you find the top K and heavy hitters?
8
20.7 How do you choose size vs error rate?
9
20.8 Where does each one show up in interviews?
10
Memory card and where the analogy breaks
11
Practice: five levels
12
Interview questions
13
Solutions
14
Sources
15
Code lab
20. Probabilistic Data Structures

Sources

3 min read+10 XP

Source notes

  • Bloom filters: Burton H. Bloom, "Space/Time Trade-offs in Hash Coding with Allowable Errors", Communications of the ACM, 1970. Sizing formulas are the standard results; numbers computed by the chapter's code.
  • Counting Bloom filters: Li Fan et al., "Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol", 2000.
  • HyperLogLog: Philippe Flajolet et al., "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm", 2007 (standard error ≈ 1.04/√m). Redis HyperLogLog: up to 12 KB per key, 0.81% standard error, PFADD/PFCOUNT/PFMERGE: Redis documentation, checked 2026-10-08.
  • Count-min sketch: Graham Cormode and S. Muthukrishnan, "An Improved Data Stream Summary: The Count-Min Sketch and its Applications", 2005.
  • Space-Saving: Ahmed Metwally, Divyakant Agrawal and Amr El Abbadi, "Efficient Computation of Frequent and Top-k Elements in Data Streams", 2005. Misra-Gries: Jayadev Misra and David Gries, "Finding Repeated Elements", 1982.
  • Bloom filters per SSTable in Cassandra and RocksDB: Apache Cassandra and RocksDB documentation.
  • Account, visitor and search volumes are illustrative assumptions; arithmetic computed 2026-10-08.
  • Level 3 and Level 4 code: tested 2026-10-08 (code/ch20_probabilistic.py, all checks pass).