Probabilistic Data Structures: Bloom Filter, HyperLogLog, Count-Min Sketch
Approximate answers in very little memory: 'this item is probably present or definitely absent', 'how many unique users', 'how many times each item appeared'.
55.1 Why is it used?
- Storing crores of items exactly is expensive: a set of 100 crore unique user IDs takes GBs, while HyperLogLog takes only ~12 KB.
- Avoid useless lookups on the DB/disk: a Bloom filter tells you first that a key is definitely absent, so the disk read is skipped.
- Real-time analytics: unique visitors, trending hashtags, top products; a small error is fine but speed and memory matter.
- Fast membership tests: is the username available, was the URL already crawled, check against a malicious URL list.
- In streaming data (Kafka events), get counts and frequencies without storing every event.
55.2 How it works
- Bloom Filter: an array of m bits + k hash functions; on add set k bits to 1, on check if all k bits are 1 the answer is 'probably present', if any is 0 it is 'definitely absent'.
- A Bloom filter can give false positives but never false negatives; a normal Bloom filter cannot delete (a Counting Bloom / Cuckoo filter can).
- Bloom sizing: about 10 bits per item and 7 hash functions give a ~1% false positive rate.
- HyperLogLog: estimates the unique count (cardinality) by counting the leading zeros of hashes; Redis HLL gives ~0.81% standard error in ~12 KB.
- HyperLogLogs can be merged: merge daily HLLs to get weekly unique users (PFMERGE).
- Count-Min Sketch: d rows x w counters, a different hash per row; on add increment one counter in every row, on query the minimum across rows = approximate frequency.
- Count-Min only over-estimates (it never reports lower); it is used with a heap for Top-K/heavy hitters.
- Trade-off: memory vs error rate; for lower error you need more memory; if you need an exact answer, do not use these structures.
- 1.BF.ADD seen:user7 clip42: h1, h2, h3 set three bits to 1 (bit array m=16: 0010000100010100)
- 2.BF.EXISTS clip42: all 3 bits are 1 -> 'PROBABLY present', a false positive is possible, skip the clip
- 3.BF.EXISTS clip99: bit 4 = 0 -> 'DEFINITELY absent', never a false negative, recommend it
Sizing: ~10 bits/item, 7 hashes -> ~1% false positive. Deletion is not possible (you need a Counting Bloom / Cuckoo filter). Used elsewhere: Cassandra skips SSTable disk reads, crawlers track seen URLs.
- 1.Play events (crores, from Kafka)
- 2.PFADD match:final userId -> a Redis HLL key, fixed ~12 KB, no matter how many users
- 3.PFCOUNT every minute -> Dashboard 'X crore watching'
A ~0.81% error is acceptable. PFMERGE: daily -> weekly unique. An exact set = GBs of RAM; BigQuery APPROX_COUNT_DISTINCT is also HLL.
- 1.clip7 view -> CMS.INCRBY clip7 1
- 2.With hash 1, hash 2, hash 3, one counter in each of d = 3 rows x w = 6 counters is incremented (rows: 2 0 5 1 0 3 / 0 7 1 0 4 2 / 1 3 0 0 5 2)
- 3.CMS.QUERY clip7 = min(5, 7, 5) = 5; only over-estimates, never lower
- 4.Top-K heap -> Trending clips list, without keeping an exact counter per clip
55.3 Tools
| Tool | Type | How it is used |
|---|---|---|
| Redis (HyperLogLog) | In-memory store | Built-in PFADD visitors:2026-10-11 user123, unique count via PFCOUNT, merge days via PFMERGE. |
| Redis Stack / RedisBloom | Redis module | BF.ADD, BF.EXISTS (Bloom), CF.* (Cuckoo), CMS.INCRBY / CMS.QUERY (Count-Min), TOPK.* commands. |
| Google Guava | Java library | BloomFilter.create(Funnels.stringFunnel(UTF_8), 10_000_000, 0.01): a Bloom filter in app memory. |
| Apache Cassandra | Database (internal use) | A Bloom filter per SSTable: checked first on a read, and if the key is absent the SSTable disk read is skipped; tune with bloom_filter_fp_chance. |
| Apache DataSketches | Sketch library | HLL, Theta and frequency sketches: approximate analytics in Druid, Spark and big data pipelines. |
| BigQuery / Presto approx functions | Analytics SQL | APPROX_COUNT_DISTINCT (HLL based): much faster and cheaper than exact COUNT DISTINCT on billions of rows. |
55.4 Comparison: Bloom Filter vs HyperLogLog vs Count-Min Sketch
| Point | Bloom Filter | HyperLogLog | Count-Min Sketch |
|---|---|---|---|
| Question it answers | Is this item in the set? | How many unique items are there? | How many times did this item appear? |
| Error type | False positives possible, no false negatives | Approximate count (~0.81% in Redis) | Always over-estimates, never lower |
| Memory | ~10 bits per item (at 1% FP) | Fixed ~12 KB, however many items | Fixed w x d counters |
| Delete support | No (yes in the Counting/Cuckoo variants) | No | No (in the normal version) |
| Merge | Same-size filters merge with OR | Yes, PFMERGE is easy | Yes, by adding counters |
| Redis command | BF.ADD / BF.EXISTS (RedisBloom) | PFADD / PFCOUNT (built-in) | CMS.INCRBY / CMS.QUERY (RedisBloom) |
| Best for | Skipping cache/DB lookups, username checks, crawler seen URLs | Unique visitors, DAU/MAU | Trending items, heavy hitters, rate counting |
55.5 When to choose which
- Bloom Filter: when you must say 'not present' fast and an occasional wrong 'probably present' is fine (then check the real DB).
- HyperLogLog: when you only need the unique count, not the list: unique users of page views, daily active users.
- Count-Min Sketch: when you need the approximate frequency of very many items: trending products, top search terms.
- When an exact answer is essential (payment, inventory, billing): do not use these structures, use a normal set/counter.
- If you already have Redis use its built-in HLL; for Bloom/CMS take Redis Stack or Guava (single app).
55.6 Real-world example
An illustrative scenario: unique viewers and trending on a Hotstar IPL match.
- In the final, crores of users are streaming; every login/play event lands in Kafka.
- Unique viewers: PFADD match:final userId on every event; even for crores of users it is one key of only ~12 KB.
- Every minute PFCOUNT puts a live approximate 'X crore watching' number on the dashboard; a ~1% error is fine.
- Trending clips: CMS.INCRBY on every clip view in the Count-Min Sketch; Top-K gives the most watched clips.
- The recommendation service keeps a Bloom filter of 'user has seen this clip'; it runs BF.EXISTS before recommending again.
- If Bloom says 'not seen' it is definitely not seen; if a clip is skipped on 'probably seen' there is no real loss.
- An exact set would need GBs of RAM; the probabilistic structures did the job in a few MBs.
55.7 Interview tips
- Remember in one line: 'Bloom: no false negatives, HLL: unique count in fixed memory, CMS: frequency over-estimate'.
- Common mistake: sizing a Bloom filter without the expected item count; if more items arrive the false positive rate shoots up.
- Using an approximate structure where exactness is needed (wallet balance, stock count).
- Trying to delete from a Bloom filter: bits of other items get cleared too, causing false negatives. Numbers to quote: HLL ~0.81% error in ~12 KB, Bloom ~1% FP at ~10 bits/item.