A filter that is allowed to be wrong

Every structure on this site so far answers correctly. A hash table asked whether a key is present says yes if it is and no if it is not; the interesting questions are how many probes it took and how the count behaves as the table fills. Correctness is assumed and the cost is measured.

A Bloom filter is the first structure here that is allowed to be wrong, and it changes what has to be measured. It answers “is this key in the set?” with no, which is always right, or probably, which is right at a rate that has a closed form. The rate is a third quantity beside the operation count and the space, it is the one every sizing decision turns on, and it is checkable against a filled filter in the same way the probe formula is checkable against a hash table.

The mechanism, and where the error comes from #

A Bloom filter is an array of $m$ bits, initially zero, and $k$ hash functions. To insert a key, hash it $k$ ways and set those $k$ bits. To query a key, hash it $k$ ways and check those $k$ bits: if any is zero the key is definitely absent, and if all are one the key is probably present.

The asymmetry falls straight out of that. A key that was inserted set all its bits, and bits are never cleared, so its bits are still one — a false negative is impossible, not unlikely. A key that was never inserted can nonetheless find all $k$ of its bits set, because other keys set them, and then the filter says yes wrongly.

So the structure has one-sided error, and the side matters enormously in practice. The use everybody has is as a cheap pre-filter in front of an expensive lookup: check the filter, and if it says no, skip the disk read. A false positive costs one wasted expensive lookup, which is a performance cost. A false negative would cost a wrong answer, and there are none.

Two things to be exact about, because both get muddled.

There is no deletion. Clearing bits would break other keys’ entries and reintroduce false negatives. Counting filters replace each bit with a small counter to allow it, at several times the space; a plain Bloom filter is insert-only.

There is no way to enumerate the contents. The filter holds no keys. It holds evidence that some keys were inserted, and there is no operation that recovers them. That is a limitation and it is also the reason it is small.

Where the rate comes from #

The standard derivation is three steps and it is worth having in full, because two approximations are made in it and neither is usually mentioned.

Inserting $n$ keys with $k$ hashes performs $kn$ bit-writes into $m$ bits. The probability that a particular bit is still zero afterwards is $(1 - 1/m)^{kn}$, which is approximated as $e^{-kn/m}$. So the fraction of bits set is taken as

$$f = 1 - e^{-kn/m}$$

A query for an absent key checks $k$ bits. If each is set with probability $f$ independently, all $k$ are set with probability $f^k$, giving

$$\varepsilon = \left(1 - e^{-kn/m}\right)^k$$

which is the formula on every sizing page there is.

The two approximations are the exponential in the first step and the independence in the second. The first is easy to remove — $m(1-(1-1/m)^{kn})$ is exact and no harder to compute — and the second cannot be removed, because the $k$ probes of a query are drawn against one shared table and can land on the same bit. Whether either matters is a question for measurement, and it is the whole of the next essay. This one uses the formula and checks it.

The measurement #

Four thousand keys, four hashes, five sizes, sixty thousand queries for keys that were never inserted:

The formula is accurate to a few per cent of itself across a rate spanning a factor of twenty-six. That is a good result for a closed form with two approximations in it, and it is the reason the formula is usable.

Three readings of the table are worth making.

The rate falls exponentially in the space. Each two extra bits per element roughly halves the error at $k=4$. A structure whose accuracy improves exponentially in its size is unusual and it is the reason Bloom filters are used at all: going from 1.14% to 0.62% costs two bits per element, or 1,000 bytes on four thousand keys.

Five thousand bytes holds four thousand keys at 1.14%. Ten bits per element is 5,000 bytes for $n = 4{,}000$. A hash set of 4,000 32-bit integers with any reasonable load factor is 32 kilobytes and the filter is a sixth of that — while being wrong about one absent key in ninety, and never being wrong about a present one.

The fill is the mechanism, visibly. At four bits per element 63% of the table is set, and a random query finding four set bits at that density is not a surprise. At twelve bits per element 28% is set and $0.28^4 = 0.0062$, which is the measured rate. The rate is not mysterious; it is the density of ones raised to the fourth power.

The number of hashes is a choice, and the curve has a minimum #

$k$ appears twice in the rate expression and pulls in opposite directions. More hashes mean more bits must agree for a false positive, which helps; more hashes also mean more bits set per insertion, which hurts. The minimum is at $k = (m/n)\ln 2$, which for ten bits per element is 6.93.

The measured curve bottoms out at $k = 7$ with a rate of 0.790%, against a predicted optimum of 6.93. Two features of the shape are worth acting on.

The minimum is shallow. $k = 6$ gives 0.795% and $k = 8$ gives 0.808%. Being one hash away from optimal costs under 3% of the rate, so rounding $(m/n)\ln 2$ in either direction is free, and there is no reason to compute it precisely.

The left edge is not shallow. $k = 1$ costs 9.37%, nearly twelve times the optimum, and $k=2$ costs 3.17%. A filter with one hash function is a hash table’s occupancy bitmap, and it is a much worse filter than the same memory used properly. This is the mistake the figure exists to price: it is the one that gets made, because $k=1$ is simpler and the structure still works.

There is also a practical note the curve does not show. Each hash is a memory probe, and at eight hashes into a table larger than cache, a query is eight cache misses. So the $k$ that minimises the rate is not the $k$ that minimises the time, and real implementations often use fewer hashes than optimal and accept a worse rate — or pack all $k$ bits of a key into one cache line, which changes the analysis and is a different structure. That is the two counts disagreeing again, in a new place.

Sizing one, in the order the decisions actually come #

The three parameters are $n$, $m$ and $k$, and they are not independent — fixing any two fixes the third’s optimum. The order the decisions come in when building something is worth writing down, because the formulas are usually presented in the other order.

The rate comes first, and it comes from the application. What does a false positive cost, and how many queries will there be? A filter in front of a disk read costs one seek per false positive; at a million negative queries a second, a rate of 1% is ten thousand extra seeks a second and a rate of 0.1% is a thousand. That is an engineering budget, not a mathematical choice, and everything else follows from it.

The space follows from the rate. $m/n = \log_2(1/\varepsilon)/\ln 2$, which is $1.44\log_2(1/\varepsilon)$. For 1% that is 9.59 bits per element; for 0.1%, 14.38; for 0.01%, 19.17. Each factor of ten costs 4.79 more bits per element, forever — the relationship is logarithmic in the rate and linear in the bits, which is the good direction to be in.

The number of hashes follows from the space. $(m/n)\ln 2$, rounded either way, and the curve above says the rounding is free.

And then $n$ has to have been right. This is the parameter that causes trouble in practice, because a Bloom filter must be sized before it is filled and the rate degrades if more keys arrive than were planned for. Take the filter above — 40,000 bits, $k = 7$, sized for 4,000 keys — and put more in it:

Fifty per cent more keys costs six times the error rate; twice as many costs seventeen times. A filter that is overfilled does not degrade gracefully, and the reason is in the exponent: the rate is the fill raised to the seventh power, so a fill rising from 0.50 to 0.75 — which sounds like a half — is a rate rising by $1.5^7$. Scalable and partitioned filter variants exist for exactly this, and the plain structure’s answer is to know $n$ in advance.

The optimum sets the fill to exactly one half, and the overfill law follows #

The sizing rule $k = (m/n)\ln 2$ is usually presented as the root of a derivative, which is true and says nothing about what the filter is doing at that point. Substitute it back into the fill:

$$f = 1 - e^{-kn/m} = 1 - e^{-\ln 2} = \tfrac{1}{2}.$$

The optimal number of hashes is the number that sets exactly half the bits. Every well-sized Bloom filter is a table with half its bits on, whatever its rate, whatever its size — and the rate is then $f^k = 2^{-k}$, so $k$ is simply the number of bits of confidence bought. At $k = 7$ that is $2^{-7} = 0.781\%$ against the 0.790% measured, and the shallow minimum in the figure above is the shallowness of $f^k$ near $f = 1/2$.

That reading makes the whole space accounting one line. To reach a rate $\varepsilon$ needs $k = \log_2(1/\varepsilon)$ hashes; each hash costs $1/\ln 2$ bits per element to keep the fill at a half; so $m/n = 1.4427\log_2(1/\varepsilon)$, which is the sizing formula and its 44.27% overhead in the same breath. The gap a floor on the bits prices is the cost of holding the table at one half rather than at whatever an optimal code would hold it at.

It also turns the overfill table into a closed form with nothing fitted in it. Insert $s$ times as many keys as planned, with $m$ and $k$ unchanged, and the exponent scales by $s$:

$$f(s) = 1 - 2^{-s}, \qquad \varepsilon(s) = \left(1 - 2^{-s}\right)^{k}.$$

At $s = 1.5$ that is a fill of 0.6464 and, at $k = 7$, a rate of 4.72%; at $s = 2$, a fill of exactly 0.75 and a rate of 13.35%. The measured columns are 0.6481 and 4.82%, and 0.7500 and 13.44%. The “six times” and “seventeen times” quoted above are $(0.6464/0.5)^7$ and $1.5^7$ — the same exponentiation, with no second effect hiding in them.

Differentiating at the design point gives the sensitivity that matters when sizing: a fractional overfill costs $k\ln 2 \approx 0.693k$ times that fraction in relative error, so at $k = 7$ one per cent more keys than planned is five per cent more error.

And the sign of that expression carries the warning. The exponent is $k$, and $k$ is what a tighter rate buys, so a filter designed conservatively is more fragile rather than less. At $k = 14$ — a designed rate of one in sixteen thousand — twice the planned keys gives $0.75^{14} = 1.78\%$, which is 292 times the design target, against the factor of seventeen at $k = 7$. Choosing a stricter guarantee steepens the cliff behind it.

So $n$ is not one parameter among three. It is the one the other two are computed from, it cannot be measured after the fact from the structure, and it is a count somebody chose before any key arrived — which is the precise sense in which a Bloom filter is a promise about a workload rather than about a set.

What it is spending, against what it must spend #

A filter at ten bits per element and $k = 7$ measures a rate of 0.790%. The information-theoretic floor for approximate membership at that rate is $\log_2(1/0.0079) = 6.98$ bits per element. The filter is using ten.

That 44% gap is a fixed property of the construction — $1/\ln 2 = 1.4427$ at every rate — and it is the subject of its own essay, because it is the floors field’s first bound on space rather than on time and the first bound on this site that a real structure comes anywhere near. Comparison sorting sits a few per cent above its floor and gets there with a clever algorithm; a Bloom filter sits 44% above its floor and the gap is a design choice with a name.

There is a further comparison the floor invites and the arithmetic settles quickly. A perfect hash table storing a $\log_2(1/\varepsilon)$-bit fingerprint per key would sit exactly on the floor, and it needs the perfect hash — which itself costs about 2.5 bits per element to represent and cannot be built incrementally. So the floor is not reachable by anything with a Bloom filter’s interface, and the practical question is not “how close to the floor” but “how close to the floor among structures that accept one key at a time”. Cuckoo filters and quotient filters answer that at around 1.05 to 1.2 times the floor, and they are more complicated in exactly the way the extra 25% of space buys.

The curve at three settings #

The measured circles and the printed formula are the two things on this plate, and the useful question is whether they agree at settings other than the one it was drawn at.

Six is between the two, and it is where the optimum sits for most of the bit budgets on the axis — which is worth drawing before the argument about choosing $k$ rather than after it.

The next two are checks rather than variations: one changes $n$ and $m$ together, which the formula says should change nothing, and one changes only the hash seed.

The independence the whole thing assumes #

Everything above assumes the $k$ hash functions behave like independent uniform random maps. They are not — they are two multiplications and a shift each — and the measurement is what says the assumption survives.

It nearly did not. The first version of the hash used here reduced into the table with (a·x + b) mod m for a power-of-two $m$, which takes the low bits of the product. The low bits of a product are a function of the low bits of its operands alone, so the four hashes were correlated, and the filter measured a false-positive rate of 12.96% where the bits it had set predicted 2.72% — a factor of 4.8, on a structure that drew perfectly well and passed every other check. Taking the high bits instead, which is one more multiply, brings the measured and predicted rates to within 1.3% of each other.

That defect was found by an assertion — assertBloomMatchesItsBits, which compares the measured rate against the estimate made from the bits the filter actually has set — before a single figure was drawn. It is worth naming what makes that assertion able to catch it: it does not compare the measurement against the textbook formula, which involves an assumed fill and would have muddled two questions. It compares against a prediction made from the fill this filter measured, which isolates the independence assumption on its own.

What a filter is for, and what it is not #

It is worth ending on the shape of the trade rather than on the arithmetic, because the arithmetic is the easy part.

A Bloom filter is the right structure when three things hold at once: the set is large enough that holding it exactly is expensive, a false positive is cheap — it costs a wasted lookup rather than a wrong answer — and a false negative would be unacceptable. That combination is common in one specific place, which is in front of something slow: a disk, a network, a cold cache. Every use that made Bloom filters famous is of that shape.

It is the wrong structure when any of the three fails. If false positives are not cheap, the rate is a correctness budget rather than a performance one and needs to be set accordingly small, which costs bits fast — $\varepsilon = 10^{-6}$ needs 28.8 bits per element, which is not obviously less than storing the keys. If the set is small, an exact structure fits anyway. And if deletion is needed, the plain filter cannot do it.

The honest summary is that a Bloom filter trades a specific, quantified, one-directional wrongness for a large constant factor of space, and that the quantification is the part worth insisting on. The rate is not “small” or “negligible”. At the sizes above it is 16.17%, 5.53%, 2.45%, 1.14% and 0.62%, each measured against sixty thousand queries, and each within a few per cent of a formula that can be evaluated before anything is built.