Building Blocks

Bloom Filters, HyperLogLog & Count-Min Sketch

Some questions don't need exact answers: "have we probably seen this URL before?", "roughly how many unique visitors today?", "which items are the most frequent?". Probabilistic data structures answer them in a tiny, fixed amount of memory by accepting a small, controlled error. At the scale of billions of items, that trade is often the only practical one.

In simple words

A bouncer with a quick memory who can say "definitely not seen you before" for sure, but occasionally says "I think I've seen you" wrongly. It uses tiny memory and is almost always right, which is perfect when an occasional wrong guess is cheap.

A tiny filter answers most questions; only "maybe" answers pay for the real lookup.

Deep Dive: Bloom Filter — "Definitely Not" or "Probably Yes"

bit array of m bits, k hash functions

add(x):     set bits h1(x) .. hk(x) to 1
contains(x): all k bits set?  no  -> DEFINITELY not in the set
                              yes -> PROBABLY in the set (false positive possible)

m = 16 bits, k = 3
add("goa"):  bits 2, 7, 11      add("delhi"): bits 4, 7, 13
check("pune"): bits 2, 4, 9 -> bit 9 is 0 -> definitely not present
check("agra"): bits 2, 11, 13 -> all 1 -> "probably" (a false positive here)

Rule of thumb: ~10 bits per element with k ~ 7 gives ~1% false positives.
No false negatives. Standard Bloom filters can't delete (counting variants can).

Uses: a web crawler skipping URLs already seen; a database (LSM-tree stores like Cassandra, RocksDB) skipping disk files that can't contain a key; checking "is this username taken?" before a database lookup; filtering known-bad URLs.

Deep Dive: HyperLogLog — Counting Distinct Items

Counting unique visitors exactly needs memory proportional to the number of visitors. HyperLogLog hashes each item and tracks, in each of many small registers, the longest run of leading zeros seen; long runs are rare, so they reveal how many distinct items passed through. A few kilobytes estimate cardinalities in the billions with roughly 1% standard error, and two HLLs merge by taking register maxima (so per-hour counts combine into per-day counts). Redis offers it as PFADD / PFCOUNT / PFMERGE.

Deep Dive: Count-Min Sketch — Approximate Frequencies

d rows x w counters, one hash function per row
add(x):   for each row i: counts[i][h_i(x)] += 1
count(x): min over rows of counts[i][h_i(x)]

Collisions only ever ADD to counters, so the estimate never undercounts;
taking the minimum across rows limits the overcount.

Uses: heavy hitters / top-K (trending hashtags, most-requested keys, abusive IPs), combined with a small heap of current leaders.

Key Pointers

Bloom filter: set membership; false positives yes, false negatives never.
HyperLogLog: distinct count in ~KB with ~1% error; mergeable.
Count-min sketch: frequency estimates that only overcount; good for top-K.
Use them to avoid expensive work (a disk read, a DB query), not as the source of truth.

Follow-up Questions

Why can't a Bloom filter have false negatives?: Bits are only ever set, never cleared, so every bit an added item set is still 1 when you check it. A "no" means some required bit is 0, which is impossible for an added item.
How would you count daily unique visitors for 10,000 pages?: One HyperLogLog per page per day (≈12 KB each in Redis), PFADD on each visit, PFCOUNT to read; merge days for weekly counts. Exact sets would need memory per visitor per page.

Trade-offs

You trade exactness for orders of magnitude less memory and time. That is right for dedup hints, analytics and trending lists, and wrong for billing, balances or anything where one error matters.