probabilistic-data-structures
4 free lessons tagged probabilistic-data-structures across Computer Science. Each one is a short sequence of focused steps with narration and a five-question quiz at the end — take them in any order, no signup required.
Count-Min, and Why Sketches Compose
The count-min sketch estimates how often an item occurred using a fixed grid of counters, and it never underestimates. This lesson builds it, states the error bound that makes it usable, shows where it is useless, and ends on the property shared by all three structures that explains why they run distributed systems.
HyperLogLog: Counting Distinct Items in Kilobytes
Counting distinct items exactly needs memory proportional to the count. HyperLogLog answers the same question in a fixed twelve kilobytes, for cardinalities into the billions, by measuring an improbable event rather than storing anything. This lesson builds that idea from the leading-zeros intuition up.
Bloom Filters: Membership in a Bit Array
A Bloom filter answers set membership using a bit array and a handful of hash functions, with no items stored anywhere. This lesson builds it, derives the sizing formula that trades memory against false positives, explains exactly why deletion is impossible, and covers the variants that buy it back.
The Bargain: Bounded Memory for Bounded Error
Answering set questions exactly costs memory proportional to the data, which fails once the data does not fit. Probabilistic data structures accept a quantified error in exchange for memory that stays constant. This lesson establishes what that trade buys, and why the shape of the error matters more than its size.