The evidence a filter cannot remove

A filter allowed to be wrong sets out the bargain. A Bloom filter answers membership in a few probes and a few bits per key, gets some of its positive answers wrong, and never gets a negative one wrong. That asymmetry is the whole design: a no is certain and a yes is a maybe, so the structure can be used as a gate in front of something expensive.

The asymmetry is not a property of the data structure. It is a property of the fact that the structure only ever sets bits. A key’s presence is recorded by setting $k$ bits, nothing ever clears one, so any key that has been inserted still has all of its bits set and the filter cannot say no about it.

Take away the “nothing ever clears one” and the guarantee goes with it.

Deletion is not an exotic requirement. A cache wants to forget an evicted key; a set of active sessions wants to forget an expired one; a filter in front of a mutable index has to track deletions or it drifts. The standard advice — Bloom filters do not support deletion — is correct and is usually where the discussion stops, and what this page is about is the three things that happen when it does not stop there.

Why the bits cannot simply be cleared #

A key sets $k$ bits chosen by $k$ hashes. Two keys’ bit sets overlap whenever any of their hashes agree, and at the usual sizing — around ten bits per key, four hashes — a large fraction of set bits are shared.

Clearing a key’s bits therefore clears bits that other keys need. The filter’s answer for those other keys becomes no, they are still in the set, and the one guarantee the structure offered is gone.

The measurement puts a number on it. At sixteen thousand bits, four hashes and two thousand keys — a comfortable sizing where the false-positive rate before deletion is well under one per cent — deleting half the keys by clearing their bits makes the filter deny 638 of the 1,000 keys that remain. Nearly two thirds of the surviving set has been lost, from an operation that looks locally reasonable at every step.

It is worth being clear that this is not a marginal effect that better parameters would fix. More hashes make it worse, because each key sets more bits and therefore collides with more other keys: at six hashes the loss is 903 of 1,000. More bits make it better and not enough — doubling the filter to thirty-two thousand bits takes the loss from 638 to 396, still nearly forty per cent.

There is a rough calculation that predicts the measurement and is worth doing, because it says the effect is structural rather than a matter of luck. At $m$ bits, $k$ hashes and $n$ keys, a given bit is set with probability about $1 - e^{-kn/m}$ — 0.39 at the sizing here. Deleting half the keys clears $kn/2$ bit-positions; a surviving key needs all $k$ of its bits to escape every one of those, and its chance of doing so is roughly $(1 - \tfrac{1}{2}\cdot 0.39)^{k}$ raised over the overlaps, which at four hashes lands in the region of a third. The measurement gives 362 survivors of 1,000. The arithmetic and the run agree, so nothing about this depends on the seed.

The counting repair, and what four bits buy #

The obvious fix is to replace each bit with a small counter. Insertion increments $k$ counters, deletion decrements them, and a key is present when all $k$ of its counters are non-zero. A counter reaching zero means no key needs that cell, so clearing it is safe.

It works. In the measurement above the counting filter loses none of the surviving keys, and its false-positive rate is comparable to the Bloom filter’s — 42 wrong yeses in twenty thousand queries of absent keys, against 14, the difference being that the Bloom filter’s cleared bits have made it artificially sparse. The formula everybody sizes filters with is the essay about how closely that rate tracks its closed form, and it tracks it here too.

The price is space. A counter needs enough bits not to overflow, and four is the standard choice — the probability that a cell is touched more than fifteen times is negligible at ordinary loads. So the structure costs four times the bits for the same number of cells: 65,536 against 16,384 in the measurement, for a filter holding the same keys with the same error rate.

That is a large price and there is a second, subtler one. A counter that reaches its maximum cannot be incremented, so it must saturate — and a saturated counter can never be safely decremented again, because it has lost the count of how many keys need it. The structure therefore has a second failure mode with its own probability, controlled by the counter width, and choosing four bits is choosing a probability rather than eliminating a possibility.

The counting filter is also worth placing against the rest of this field, because it is the only structure here whose extra space buys nothing except an operation. A Bloom filter’s bits buy an error rate; a cuckoo table’s spare slots buy a build that terminates; a skip list’s levels buy a search. Four-bit counters buy deletion and nothing else — the same error rate, the same probe count, the same asymptotics, at four times the bits. That is an unusually clean price tag and it is the reason the structure is easy to reason about and rarely used: four times the space is a great deal to pay for one method.

The fingerprint repair, and the condition it adds #

The third structure stores, instead of bits, a short hash of the key — a fingerprint — in one of two slots chosen by the mechanism of the previous rung. A lookup reads both slots and looks for the fingerprint. A deletion reads both slots and removes one copy of it.

That deletes correctly, it loses none of the surviving keys in the measurement, and it costs about twice the bits rather than four times — 32,768 against 16,384. On the face of it, it dominates the counting filter.

It does not, and the reason is a precondition rather than a resource.

A deletion removes one copy of a fingerprint. It does not check that the key was ever inserted. So removing a key that was never in the set removes some other key’s fingerprint — the other key having happened to hash to the same slot with the same short hash — and a false negative appears in a structure whose entire guarantee was that it could not have one.

Measured: after removing a thousand keys that were never inserted, 15 of the 2,000 keys that were inserted are gone. Not many, and not zero, and there is no signal of any kind.

So the three structures are not ranked; they are three different contracts:

Bloom’s inability to delete is not a defect the other two fix. It is the price of an interface with no precondition, and the two newer structures move the precondition rather than removing it — one onto space, the other onto the caller.

What one-sided means, and why losing it is worse than it sounds #

A structure with one-sided error can be used as a filter in front of an exact check. The filter says no and the query stops; the filter says yes and the expensive check runs and settles it. Every false positive costs a wasted check and nothing else, so the error rate is a performance parameter.

A structure with two-sided error cannot be used that way at all. If a no can be wrong, the expensive check has to run on the negatives too, and the filter has stopped filtering.

That is why the 638 lost keys are worse than a false-positive rate of 638-in-1,000 would be. A filter with a terrible false-positive rate is a slow filter. A filter with any false-negative rate is not a filter — the whole architecture it sits in stops being valid, and the failure is silent: the system returns fewer results, and nothing in it is in a position to notice.

That distinction is the same one a distance that is not a distance draws about a broken triangle inequality, and the edit that reaches back two rows about a distance that is not a metric. In each case a property that seems like a nicety turns out to be what an entire class of structures is resting on, and losing it costs candidates rather than time.

The fourth option, which is to not delete #

There is a way out that none of the three structures above takes and that a great many systems use, and it belongs on the page because it is often the right answer.

Keep a second filter of the deleted keys. A query consults both: present in the first and absent from the second means yes, present in both means no. Both filters retain the one-sided guarantee, since neither ever clears a bit, and the composition’s error is the two filters’ errors combined — a key wrongly reported present in the deletion filter is a false negative overall, so the guarantee is one-sided in a different direction and the composition is two-sided after all.

Or rebuild periodically. Insert into a fresh filter from the live key set at intervals, and accept that deletions take effect at the next rebuild. That keeps both guarantees exactly, costs a pass over the data, and is what most production systems in front of a mutable index do.

Both options are worth naming because they change what the plates mean. The measurement on this page says what the three in-place structures cost. It does not say that deletion must be paid for in the structure, and a system that can tolerate stale negatives for a few minutes can have the whole thing for free.

That is the same shape as several results elsewhere in this collection: the expensive version of an operation is often the version that insists on doing it immediately, and the writes nobody counted is the external-memory field’s version of exactly that observation.

How the failure would be found in a running system #

The 15 lost keys from a thousand spurious deletions are worth one more paragraph, because the number is small and the way it manifests is the point rather than the size.

There is no exception, no counter, no log line. The structure returns no for a key it holds, the caller believes it — that is what a filter is for — and the expensive check the filter was protecting is never run. A lookup that should have found something returns nothing.

Downstream, that looks like a data problem rather than a structure problem. A record is missing; somebody checks the record and it is there; somebody checks the index and it is there; the filter is the one component nobody suspects, because it is described as an optimisation and optimisations are assumed not to change answers.

A structure whose failure mode is a missing result is a structure that will be blamed last. That is the argument for the table above being three contracts rather than three performance points, and it is why the precondition belongs in the same column as the bits: one of them costs memory and the other costs an invariant somebody has to maintain in code the structure cannot see.

Where the bits actually go #

It is worth checking these three against the floor, since this field has one.

A floor on the bits computes the information-theoretic minimum for approximate membership at error rate $\varepsilon$: $n\log_2(1/\varepsilon)$ bits, with a Bloom filter costing $1/\ln 2 = 1.44$ times that. The fingerprint structures reach about 1.05 to 1.2 times the floor, which is where the 25% of space they save comes from — and that essay already notes it.

What that essay does not say, and this page measures, is that the saving and the deletion are the same feature. A fingerprint filter is cheaper because it stores the key’s identity rather than the positions it happened to occupy, and it can delete for exactly the same reason: an identity can be removed and a position cannot be attributed. The two advantages are one advantage, and so is the disadvantage — a stored identity can be removed by anybody who can compute it, whether or not they put it there.

What is not measured here #

The counter width is fixed at four. No sweep here finds where saturation starts to matter, which is a function of the load and the number of hashes and is the parameter that decides whether the counting filter’s second failure mode is real.

Only one deletion pattern is drawn, which is the same limitation a corpus that was not generated records for a different field: a generated workload has the statistics it was given. Half the keys, deleted in insertion order. A workload that inserts and deletes continuously — which is the workload deletion exists for — reaches a steady state this experiment does not visit, and the counting filter’s counters drift in it.

Nor is the fourth option measured. The two-filter and periodic-rebuild strategies above are described and not drawn, and the first of them in particular has a composed error rate that is computable and is not computed here.

And the fingerprint filter’s own failure to build is not shown. It inherits the previous rung’s threshold: a table filled past its load factor cannot place a fingerprint at all. The measurement here runs well below it, so the structure never fails, and the plate is silent about a failure mode the page before this one is entirely about.

What the three structures say about approximate answers generally #

Standing back from the bits, the page has measured something more general than a comparison of three filters, and it is worth stating in the form it takes.

An approximate structure is defined by which of its answers can be wrong. That is the design, and everything else — the space, the probe count, the constant — is an implementation of it. A Bloom filter’s design is positives may be wrong; a counting filter’s is the same design with an operation added; a fingerprint filter’s is the same design again with the wrongness relocated onto a precondition.

What this page shows is that the design is fragile in a specific way: it is preserved by every operation the structure was defined with, and an operation added later can destroy it silently. Deletion is not a new implementation of an existing contract; it is a different contract, and the three structures are three ways of noticing that.

The general form is a question worth asking of any approximate structure. What can this be wrong about, and does every operation preserve that? A sketch that answers frequency queries, an index that answers nearest-neighbour queries approximately, a filter that answers membership — each has a direction of error, each is used in an architecture built around that direction, and each has operations that were added after the guarantee was stated.

This collection has one instance of the same shape in a different field: a distance that is not a distance, where a cost model removes the triangle inequality and takes with it every structure that prunes by distance. In both cases the loss is a property rather than a number, it is invisible in every output, and the architecture that depended on it does not stop working — it starts returning less.

Where this ladder goes from here: the filter that is asked a different question #

Every structure on this page answers is this key in the set. That is one question, and the structures around it in practice answer several others that this ladder has not touched.

How many times has this key been seen is what a counting sketch answers, and the streaming field has that. Is this key in the set, and if so where is what a fingerprint structure could answer and a Bloom filter cannot, since a set bit names no key. And what is the intersection of these two sets is a question a Bloom filter answers by bitwise-and — approximately, with an error rate that is not the same as either filter’s and which nobody quotes.

That last one is the interesting rung, because it is a place where the composition of two approximate answers has an error nobody derives. Intersecting two filters gives a filter of the intersection plus every key whose bits happen to be set in both, and the rate of that is a function of both filters’ loads rather than of either one’s stated error. It is measurable by the same enumeration this page uses, it is used in real systems to intersect sets across machines, and the number it produces is not the number either filter advertises.