Probabilistic Data Structures: Bloom Filters, HyperLogLog, Count-Min Sketch

Probabilistic data structures answer queries approximately, using far less memory than an exact structure and with a bounded, quantifiable error. They suit workloads where the data set is too large to hold exactly, such as billions of keys or unbounded streams, and where a small error rate is acceptable.

Bloom filter

A Bloom filter tests set membership. It never returns a false negative: if it says "not present", the element was definitely not added. It can return a false positive: "possibly present" for an element that was never added.

How it works

The filter is a bit array of m bits, all zero initially, plus k independent hash functions.

• Add(x): compute h1(x) ... hk(x), each modulo m, and set those k bits to 1.
• Contains(x): compute the same k positions. If all bits are 1, answer "possibly present". If any is 0, answer "definitely absent".

flowchart LR
    x["add 'cat'"] --> h1["h1 = 1"] & h2["h2 = 5"] & h3["h3 = 9"]
    y["query 'dog'"] --> g1["h1 = 5"] & g2["h2 = 9"] & g3["h3 = 12"]
    g3 --> z["bit 12 is 0, so 'dog' is definitely absent"]

Elements cannot be removed, because clearing a bit could erase evidence of other elements.

Error rate and sizing

After inserting n elements into m bits with k hash functions, the false positive probability is approximately:

p ≈ (1 - e^(-kn/m))^k

For a target p and expected n:

• Bits: m = -n ln(p) / (ln 2)^2
• Hash functions: k = (m / n) ln 2

Rules of thumb from these formulas:

So 100 million keys at 1% needs about 120 MB, regardless of key size, while storing the keys themselves takes at least that many times their length in bytes. Check: n = 1000, m = 9586, k = 7 gives kn/m = 0.73, e^-0.73 = 0.482, and (1 - 0.482)^7 is about 0.010, matching the 1% target. Exceeding the planned n raises the false positive rate quickly. Scalable Bloom filters chain additional filters as the set grows.

Uses

• LSM-tree storage engines (Cassandra, RocksDB, HBase, LevelDB): each SSTable has a Bloom filter so a read for an absent key skips most files without disk I/O. See storage engines.
• Cache penetration protection: reject requests for keys that do not exist before they reach the database.
• Crawlers and deduplication: "has this URL been seen?" where an occasional false positive (skipping a page) is tolerable.
• Distributed joins: send a filter of one side's keys to avoid shipping non-matching rows.

Java implementation

Double hashing derives the k positions from two base hashes: h_i = h1 + i * h2. The example uses a fixed FNV-1a hash so output is deterministic.

import java.nio.charset.StandardCharsets;

public class Main {
    static final class BloomFilter {
        private final long[] bits;
        private final int m;
        private final int k;

        BloomFilter(int expectedItems, double falsePositiveRate) {
            double ln2 = Math.log(2);
            this.m = (int) Math.ceil(-expectedItems * Math.log(falsePositiveRate) / (ln2 * ln2));
            this.k = Math.max(1, (int) Math.round((double) m / expectedItems * ln2));
            this.bits = new long[(m + 63) / 64];
        }

        int bitCount() {
            return m;
        }

        int hashCount() {
            return k;
        }

        static long fnv1a(byte[] data, long seed) {
            long hash = 0xcbf29ce484222325L ^ seed;
            for (byte b : data) {
                hash ^= (b & 0xffL);
                hash *= 0x100000001b3L; // long arithmetic wraps on overflow
            }
            return hash;
        }

        private int[] positions(String item) {
            byte[] data = item.getBytes(StandardCharsets.UTF_8);
            long h1 = fnv1a(data, 0);
            long h2 = fnv1a(data, 0x9e3779b97f4a7c15L) | 1;
            int[] result = new int[k];
            for (int i = 0; i < k; i++) {
                result[i] = (int) Long.remainderUnsigned(h1 + i * h2, m);
            }
            return result;
        }

        void insert(String item) {
            for (int pos : positions(item)) {
                bits[pos / 64] |= 1L << (pos % 64);
            }
        }

        boolean contains(String item) {
            for (int pos : positions(item)) {
                if ((bits[pos / 64] & (1L << (pos % 64))) == 0) {
                    return false;
                }
            }
            return true;
        }
    }

    public static void main(String[] args) {
        var filter = new BloomFilter(1000, 0.01);
        System.out.println("bits: " + filter.bitCount() + ", hash functions: " + filter.hashCount());

        for (int i = 0; i < 1000; i++) {
            filter.insert("user-" + i);
        }

        int missing = 0;
        for (int i = 0; i < 1000; i++) {
            if (!filter.contains("user-" + i)) {
                missing++;
            }
        }
        System.out.println("false negatives: " + missing);

        int falsePositives = 0;
        for (int i = 0; i < 10_000; i++) {
            if (filter.contains("other-" + i)) {
                falsePositives++;
            }
        }
        System.out.println("false positives out of 10000: " + falsePositives);
    }
}

bits: 9586, hash functions: 7
false negatives: 0
false positives out of 10000: 41

long multiplication wraps on overflow, which FNV-1a relies on, and Long.remainderUnsigned keeps the position non-negative when the hash has its top bit set. The theoretical false positive rate for these parameters is about 1%. The observed count depends on the hash function and the test keys. The false negative count is always zero.

Counting Bloom filter

A counting Bloom filter replaces each bit with a small counter (commonly 4 bits). Add increments the k counters, remove decrements them, and a query checks that all are nonzero. This supports deletion at several times the memory. Counter overflow must be handled (saturate and never decrement a saturated counter). Deleting an element that was never added corrupts the filter. Cuckoo filters are an alternative that supports deletion with comparable space.

HyperLogLog

HyperLogLog (HLL) estimates the number of distinct elements (cardinality) in a stream using a few kilobytes.

How it works

1. Hash each element to a uniformly distributed bit string.
2. Use the first b bits to choose one of m = 2^b registers.
3. In the remaining bits, count the position of the first 1 bit (the number of leading zeros plus one). Store the maximum of this value per register.
4. A long run of leading zeros is rare: seeing a run of r zeros suggests about 2^r distinct elements. Averaging over many registers (with a harmonic mean and bias corrections) reduces variance.

The standard error is about 1.04 / sqrt(m). Redis's PFADD/PFCOUNT uses 16384 registers, a fixed size of up to about 12 KB, with a standard error of 0.81%, regardless of whether it counts thousands or billions of items.

Properties:

• Fixed memory independent of cardinality.
• Mergeable: the union of two HLLs is the register-wise maximum. This supports distributed counting (per-shard sketches merged at query time) and unique-visitor counts over time windows.
• Not able to list or test membership. Intersection is only estimable indirectly, with larger error.
• No deletion.

Uses: unique visitors per page, distinct users per day, distinct-value estimates in query planners and analytical databases (BigQuery, Presto, Redis, Druid).

Count-Min sketch

A Count-Min sketch estimates the frequency of each element in a stream.

How it works

It is a two-dimensional array of counters with d rows and w columns, and one hash function per row.

• Update(x, c): for each row i, increment counter[i][h_i(x)] by c.
• Estimate(x): return the minimum over rows of counter[i][h_i(x)].

Collisions can only add to a counter, so every counter is at least the true count. The estimate therefore never underestimates. The minimum across rows picks the row with the least collision noise.

flowchart TD
    x["update 'page-7'"] --> r1["row 1: h1 selects column 3, add 1"]
    x --> r2["row 2: h2 selects column 0, add 1"]
    x --> r3["row 3: h3 selects column 6, add 1"]
    q["estimate 'page-7'"] --> m["min of the three counters"]

Error bound

With w = ceil(e / ε) columns and d = ceil(ln(1 / δ)) rows, where N is the total of all counts:

• The estimate is at most true + ε N, with probability at least 1 - δ.
• The estimate is never less than the true count.

Example: ε = 0.001 and δ = 0.01 give w = ceil(e / 0.001) = 2719 columns and d = ceil(ln 100) = 5 rows. That is 13,595 counters, about 54 KB with 4-byte counters, and the estimate exceeds the true count by more than 0.001 N with probability at most 1%. For a stream of N = 10^9 events, the error bound is 10^6, so an item must occur well above a million times to be estimated with small relative error.

The error is relative to the total stream size, so the sketch is accurate for heavy hitters (items with frequency well above ε N) and unreliable for rare items.

Uses: top-k trending items (paired with a small heap of candidates), network flow volume, rate limiting and abuse detection over many keys, and frequency estimates in query optimizers. Redis Stack provides CMS.* commands.

Comparison

Interview questions

• Why can a Bloom filter produce false positives but never false negatives? Bits are only ever set, never cleared. A present element always has all k bits set. A different element can find its k bits set by other elements' insertions.
• How do you size a Bloom filter? Choose the expected element count n and target rate p, then m = -n ln p / (ln 2)^2 bits and k = (m/n) ln 2 hashes. About 9.6 bits per element gives 1%.
• Why is HyperLogLog mergeable and why does that matter? Each register holds a maximum, and the maximum of maxima equals the maximum of the combined stream. Shards can each keep a sketch and combine them without reprocessing data.
• When would you use Count-Min sketch instead of a hash map? When the key space is too large to store a counter per key, and the application needs approximate counts for frequent items, such as top-k or abuse detection.