Probabilistic Data Structures

Some questions are expensive to answer exactly at scale. How many distinct users visited today? Has this URL been crawled before? Which API keys are sending the most requests? Answering them precisely means storing every user ID, every URL, or a counter per key — gigabytes of memory for a number you only need to be roughly right.

Probabilistic data structures answer these questions approximately, with bounded error, in a small and often fixed amount of memory. A HyperLogLog counts billions of distinct items within about 1% using 12 KB. A Bloom filter tells you whether an item is definitely absent or probably present using about 10 bits per item. They power database storage engines, caches, stream analytics, and deduplication everywhere — and they are safe to use once you understand exactly which kind of error each one makes.

TL;DR

Quick Example

A Bloom filter sized for one million items with a 1% false-positive rate:

Distinct counting with Redis's built-in HyperLogLog:

Each Redis HyperLogLog uses at most 12 KB regardless of how many items are added, with a standard error of 0.81%.

Core Concepts

The Trade

All of them rely on hashing (see Hash Tables), and most are mergeable: sketches built on different machines or time windows combine into one, which makes them ideal for distributed systems.

Bloom Filters

A Bloom filter is a bit array of size m and k hash functions. Adding an item sets k bits; checking an item tests them. If any bit is 0, the item was never added. If all are 1, it was probably added — or other items happened to set those bits.

For n items, the false-positive rate is approximately (1 − e^(−kn/m))^k. The optimal number of hash functions is k = (m/n) · ln 2, and the bits needed per item are about 1.44 · log₂(1/p): roughly 9.6 bits for 1%, 14.4 bits for 0.1%. The filter's error rate rises as you add more items than it was sized for, so plan capacity — or use scalable Bloom filters that add layers as they fill.

Bloom filters cannot delete: clearing bits could remove other items. Counting Bloom filters replace bits with small counters, and cuckoo filters store fingerprints in a cuckoo hash table, supporting deletion with similar space efficiency.

Count-Min Sketch

A count-min sketch is a d × w grid of counters with one hash function per row. Incrementing an item adds to one counter in each row; the estimate is the minimum across rows. Collisions only add, so estimates never undercount. With w = ⌈e/ε⌉ and d = ⌈ln(1/δ)⌉, the estimate exceeds the true count by at most ε times the total count with probability 1 − δ. Combined with a small heap, it finds heavy hitters — the top clients, URLs, or keys in a stream.

HyperLogLog

HyperLogLog hashes each item and looks at the number of leading zeros: seeing a hash with many leading zeros suggests many distinct items have been seen. It splits items into m registers and combines their estimates with a harmonic mean, giving a standard error of about 1.04/√m. Redis, PostgreSQL extensions, BigQuery (APPROX_COUNT_DISTINCT), and most analytics databases use it for approximate distinct counts.

MinHash and Similarity

MinHash summarizes a set with the minimum hash values under many hash functions; the fraction of matching minimums between two signatures estimates their Jaccard similarity. With locality-sensitive hashing (LSH), it finds near-duplicate documents among millions without comparing every pair.

Quantile Sketches

Percentile latency cannot be averaged across servers. t-digest, KLL, and DDSketch keep compact, mergeable summaries that answer p50, p95, and p99 queries with small error — the basis of many observability backends.

Where They Are Used

See Database Indexing and Redis Data Structures.

Best Practices

Size From Requirements

Start from the expected item count and acceptable error, compute memory, and monitor fill or cardinality so you know when the assumptions break.

Use the Error in the Safe Direction

Bloom filters are safe as a pre-check before an exact lookup: a false positive costs one extra lookup, never a wrong answer.

Prefer Mergeable Sketches for Distributed Data

Build sketches per shard or time window and merge them, rather than shipping raw data to one place.

Use Well-Tested Implementations

Library and database implementations handle hashing quality, bias correction, and serialization; hand-written versions are for learning.

Common Mistakes

Treating "Probably Present" as Present

Overfilling a Filter

Exact Numbers From Approximate Counts

FAQ

What is a Bloom filter used for?

Fast, memory-efficient membership checks where false positives are acceptable but false negatives are not — such as skipping disk reads for keys that do not exist, or avoiding reprocessing items already seen.

Can a Bloom filter have false negatives?

No. If an item was added, all its bits are set, so the filter always reports it as possibly present. Only false positives occur — unless items are removed by clearing bits, which plain Bloom filters do not support.

How accurate is HyperLogLog?

The standard error is about 1.04 divided by the square root of the number of registers. Redis's implementation uses 16,384 registers in at most 12 KB, giving about 0.81% standard error.

When should I not use a probabilistic data structure?

When an error changes correctness: billing, access control, uniqueness guarantees, or anywhere users would notice wrong answers. Use them for pre-checks, estimates, and analytics.

What is the difference between a Bloom filter and a cuckoo filter?

Both test membership with false positives. Cuckoo filters store fingerprints in a hash table, which allows deletion and often gives better lookup performance at low false-positive rates; Bloom filters are simpler and very compact.

Related Topics

References