Bloom Filters, HyperLogLog and Count-Min Sketch

Probabilistic data structures answer questions about huge datasets using a tiny, fixed amount of memory, in exchange for a small, controllable error. "Have we seen this URL before?", "How many unique visitors today?", "Which search terms are trending?" can be answered over billions of items with kilobytes or megabytes instead of gigabytes.

Bloom filter: "definitely not" or "probably yes"

A Bloom filter tests set membership. It's a bit array of m bits and k hash functions. To add an item, set the k bits its hashes point to. To check an item, look at those k bits: if any is 0, the item was definitely never added; if all are 1, it was probably added (the bits might have been set by other items).

• No false negatives, a tunable false positive rate. About 10 bits per item gives ~1% false positives; 15 bits gives ~0.1%.
• 1 billion items at 1% error needs about 1.2 GB, versus tens of GB to store the items themselves.
• Standard Bloom filters can't delete items (clearing a bit could remove others). Counting Bloom filters and cuckoo filters support deletion.

Typical uses: skip disk reads for keys that don't exist (LSM-tree databases check a Bloom filter per SSTable; see indexing), avoid re-crawling URLs, block known-malicious URLs, and avoid recommending items a user has already seen.

HyperLogLog: counting distinct items

Counting unique visitors exactly needs memory proportional to the number of uniques. HyperLogLog estimates the count using the observation that among random hashes, the longest run of leading zeros you've seen hints at how many distinct values you've hashed. It averages many such registers to reduce error.

• About 12 KB estimates cardinalities in the billions with roughly 0.8% standard error.
• HLLs merge: union daily sketches into weekly counts, or per-server sketches into a global count, without double-counting.
• Redis provides PFADD / PFCOUNT / PFMERGE; BigQuery, Presto and Druid expose approximate distinct counts built on HLL.

Count-min sketch: frequencies

A count-min sketch estimates how often each item appears in a stream: a grid of counters with one hash function per row. Each arrival increments one counter per row; the estimate is the minimum across rows. It may overestimate (collisions add counts) but never underestimates.

• Fixed memory regardless of how many distinct items appear.
• Heavy hitters / top-K: combine with a small heap to track trending hashtags, hottest keys or most frequent search queries.
• Used for rate limiting at scale, network traffic analysis, and cache admission (TinyLFU uses a count-min-style sketch). See cache eviction.

Choosing

Use these where an approximate answer is fine and exact answers would be expensive: analytics, monitoring, pre-filters in front of exact checks. Never use them where a false positive would be harmful without an exact fallback.