Bloom filter vs HyperLogLog vs Count-Min Sketch
Hotstar wants the number of unique viewers of the IPL final, live, every few seconds. The exact answer means keeping every viewer ID seen so far: tens of millions of IDs, a few gigabytes of memory, on every node that counts. The approximate answer, correct to within about 1%, fits in 12 KB. That trade, a small error you can state in advance for a memory saving of five orders of magnitude, is what these three structures are for.
They get lumped together because all three are "probabilistic", but they answer different questions, and picking the wrong one is the usual interview mistake:
- Bloom filter: have I seen this item before? (membership)
- HyperLogLog: how many different items have I seen? (cardinality)
- Count-Min Sketch: how many times have I seen this item? (frequency)
A web crawler has fetched 5 billion URLs and must not fetch any of them twice. Storing every URL needs about 500 GB. What would you keep in memory instead, and what kind of mistake can you afford it to make?
The trade they all make#
Each one keeps a small array of bits or counters and feeds every item through a few hash functions that decide which cells it touches. Different items sometimes land on the same cells. That collision is the whole source of error, and it only ever pushes the answer in one direction, which is what makes them usable.
A Bloom filter can say "seen" for an item it never saw (a false positive), but it never says "not seen" for an item it did see. A Count-Min Sketch can overcount but never undercounts. A HyperLogLog is off by a known percentage either way, and that percentage depends only on how much memory you give it, not on how many items arrive.
So the design question is always: which mistake can this system afford? A crawler that occasionally skips a new URL because the filter wrongly says "seen" loses one page out of billions. A crawler that fetches the same URL twice in a loop can hammer a small site. One-sided error lets you choose the cheap mistake.