The Bargain: Bounded Memory for Bounded Error

Three questions come up constantly in systems that handle large volumes of data, and all three have easy exact answers that stop working at scale.

Membership. Have I seen this item before? Exactly answered by a hash set, which stores every distinct item.

Cardinality. How many distinct items have I seen? Exactly answered by the same hash set, counting its entries.

Frequency. How many times have I seen this particular item? Exactly answered by a hash map from item to counter.

Each solution stores something per distinct item, so memory grows with the number of distinct items. That is fine for thousands and untenable for billions, and it is untenable in a way no engineering fixes: the structures are not wasteful, they are storing the minimum an exact answer requires.

The alternative is to stop requiring an exact answer, and to be precise about what is given up instead.

The lower bound is worth seeing, because it explains why this is a mathematical wall rather than an implementation problem.

Consider membership over a universe of possible items. A structure that answers correctly for every possible query must distinguish every possible subset it might have been given, since two different sets have some item where their answers differ.

Counting those subsets gives the number of states the structure must be able to occupy, and the number of bits needed is the logarithm of that count. For a set of n items drawn from a large universe, that comes out proportional to n, with a constant depending on the universe size.

So any structure using less than about n times a constant must answer incorrectly on some input. That is not a warning; it is the design brief.

The question then becomes which inputs it is wrong about, how often, and in which direction. Those three choices are what separate the structures in this cursus from each other.

Being wrong is not one thing. The single most useful property of these structures is that their errors can be pushed entirely to one side.

A membership structure can be built so that it never says no to something it has seen. If the item was added, the answer is always yes. The only possible mistake is saying yes to something never added: a false positive.

That asymmetry changes how the structure is used, because it makes the answer conclusive in one direction. A no is certain. A yes is a maybe.

That turns out to be exactly the right shape for a filter in front of an expensive operation. Ask the cheap structure first. If it says no, skip the expensive check entirely and be confident. If it says yes, do the expensive check, which resolves the maybe.

The cost of a false positive is then a wasted lookup rather than a wrong answer, and the system as a whole is still exact. That pattern is why these structures are used far more often than their approximate nature suggests.

Read the two branches asymmetrically, because that asymmetry is the whole design.

The left branch is where the saving happens, and it is exact. No disk read, no network call, no wasted work, and no risk of being wrong.

The right branch costs what it would have cost anyway, plus the negligible sketch lookup. The false positive rate therefore does not control correctness; it controls only how much of the saving is realised.

That reframes the tuning question. A 1% false positive rate does not mean 1% wrong answers. It means 1% of the queries that could have been skipped were not, so 99% of the available saving was captured.

The payoff scales with how expensive the avoided operation is. Skipping a memory access is worth little; skipping a disk seek or a cross-network request is worth a great deal, which is why these structures cluster in storage engines and distributed systems.

Numbers make the trade concrete. Take one million distinct keys of sixteen bytes each.

import math

def bloom_size(n, bits_per_element):
    m = n * bits_per_element
    k = round(m / n * math.log(2))            # optimal number of hashes
    fp = (1 - math.exp(-k * n / m)) ** k
    return m // 8 // 1024, k, fp * 100        # KB, hashes, false positive %

for b in (8, 10, 12):
    kb, k, fp = bloom_size(1_000_000, b)
    print(f"{b} bits/elem -> {kb} KB, k={k}, false positive {fp:.3f}%")
# 8 bits/elem -> 976 KB, k=6, false positive 2.158%
# 10 bits/elem -> 1220 KB, k=7, false positive 0.819%
# 12 bits/elem -> 1464 KB, k=8, false positive 0.314%

The raw keys alone are about 15 MB, before any hash table overhead, which in practice multiplies it several times over.

At ten bits per element the structure is about 1.2 MB and errs under 1% of the time. That is roughly an order of magnitude smaller than the keys alone, and the gap widens with key length: the sketch cost depends on the number of items, not their size. A million 200-byte keys need the same 1.2 MB.

The rest of this path covers one structure per question, and they differ in the shape of their guarantee rather than merely in their accuracy.

The third column is the one to read. Every structure here is wrong in a predictable direction, and that predictability is what makes the output usable in a larger system.

A Bloom filter never misses a present item, so it is safe in front of a lookup. A count-min sketch never underestimates a frequency, so a threshold test on it never misses a heavy hitter. HyperLogLog is the odd one out: its error is two-sided, but bounded as a proportion of the answer.

Knowing the direction lets you reason about the whole system rather than the component, which is the difference between using these safely and using them hopefully.

These structures are called probabilistic, and it is worth being exact about what the probability is over, because the usual reading is wrong.

The data is not assumed to be random. No claim is made that items arrive in any distribution, and an adversary may choose them.

The randomness comes from the hash functions. The analysis assumes hashing spreads items uniformly and independently across the structure, and every guarantee is a statement about that spreading rather than about the input.

This has a practical consequence that shows up in production. If an attacker knows your hash function and its seed, they can construct inputs that collide deliberately, driving the false positive rate far above its analysed value. The mathematics is untouched; its assumption has simply been violated.

The defence is a keyed hash with a secret seed chosen at startup, which restores the uniformity assumption against an adversary who cannot guess it. Any sketch exposed to untrusted input needs this, and the cost is negligible compared to being wrong on demand.

The pattern is appealing enough that it gets applied where it does not belong. Four cases where an exact structure is the right answer.

The data fits. A hash set over ten thousand items costs almost nothing and is exact. Approximation here is complexity with no benefit.

A false positive is not recoverable. The filter pattern works because the expensive check resolves the maybe. If there is no ground truth to fall back on, a false positive becomes a wrong answer, and the guarantee is no longer one-sided in any useful sense.

You need to remove items. A standard Bloom filter cannot delete, for reasons the next lesson makes clear, and the variants that can cost more memory.

You need the items back. These structures answer questions about a set without storing it. None of them can enumerate what was added, and that is not a limitation to work around; it is what buys the space.

That last point is the honest summary of the bargain. You are not compressing the data. You are keeping an answer and discarding the data.