The intersection two filters cannot report

The evidence a filter cannot remove measured what a Bloom filter loses when a key is deleted by clearing its bits, and ended on a different operation that filters are used for across machines: finding what two sets have in common. Two services each hold a Bloom filter over their own keys, and instead of shipping the keys they ship the filters and combine them.

For the union the combination is exact. A Bloom filter over $A \cup B$, built with the same size and hash functions, is precisely the bitwise OR of a filter over $A$ and a filter over $B$, because every bit either set pair would set is set by one of them. That is why Bloom filters appear among the summaries that add: two can be merged into a summary of the merged data with no loss at all.

For the intersection the obvious combination is the bitwise AND, and it is not exact. This page measures by how much, in the two ways the AND gets used — as a membership filter for the intersection, and as a way of estimating how large the intersection is.

The AND keeps every shared key and is not the filter of the intersection #

The instance is two filters of 16,384 bits with four hash functions, each holding 2,000 keys, of which 500 are in both sets. Beside their AND sits a third filter of the same size and hashes, built directly on the 500 common keys — the filter the AND is imitating.

The AND has one property of a filter of the intersection for certain. A key in both sets set its four bits in both filters, so all four survive the AND, and the AND never says no to a shared key. The site’s check requires that on every instance; it is the one-sided guarantee that makes a Bloom filter usable at all, and it survives the combination.

The question is the other side — what the AND says yes to that it should not.

It is worth being clear about why anyone would expect the AND to work, because the expectation is reasonable and the reason it fails is specific. A bit in a filter over $A \cap B$ is set if and only if some key in both sets hashed there. A bit in the AND is set if and only if some key of $A$ hashed there and some key of $B$ hashed there. The two conditions agree whenever the key in $A$ and the key in $B$ are the same key — and they need not be. The AND answers “did something in $A$ and something in $B$ land on this bit”, which is a question about pairs of keys, and the intersection filter answers “did something in both land on this bit”, which is a question about single keys. On a sparse filter the two questions have nearly the same answer because collisions are rare; on a filter loaded to its design rate collisions are exactly what the false-positive rate is made of.

The plate has two rates and they are different kinds of error.

Absent keys — in neither set — pass the AND about seven times as often as they pass the direct filter. The reason is in the bit counts. The direct filter has 1,859 bits set: the bits the 500 common keys set, and nothing else. The AND has 3,232: those bits, plus every bit that some key of $A$ and some different key of $B$ happened to set in both. Those extra bits are collisions between the two sets’ private keys, and the AND cannot tell them from bits a common key set. An absent key’s four bits land among more set bits, and passes more often.

Keys in exactly one set are the query an intersection exists to answer no to — “is this key in both?” asked of a key that is only in $A$. The direct filter passes none of them. The AND passes 1.8% of them, which is about ten times its rate for absent keys.

Why a one-sided key passes so often #

The second rate has a short and exact explanation, and it says what the AND’s error depends on.

A key that is in $A$ set all of its bits in $A$’s filter. So in the AND those bits survive exactly when they are also set in $B$’s filter. The key is not in $B$, so whether they are set there is the ordinary Bloom filter question: what is the chance that $k$ positions chosen by hashing all land on bits $B$’s own keys set? That is $B$’s false-positive rate.

$B$’s filter has 6,294 bits set out of 16,384, a fraction of 0.384, and $0.384^4$ is 2.2% — which is the plate’s 1.8% within the variation of a finite sample. A one-sided key passes the AND at the false-positive rate of the other filter, and that rate is set by how many keys the other set holds, not by how many the two share.

That is the part a user of the AND is not told. The one-sided rate can be predicted without building anything: it is the false-positive rate of the larger of the two filters, which is the rate each party already knows for its own filter. So a system that intersects filters has the information to budget this error correctly before it ships a single bit, and the only mistake available is to budget it at the intersection’s size instead. A filter of the intersection built directly would have a false-positive rate set by the intersection’s size; a small intersection gives a sparse filter and a low rate. The AND’s rate for the query that matters is fixed by the sets’ sizes, and a small intersection between two large sets gets no benefit from being small. A filter has a selectivity is the theme for exactly this: the rate that matters is a function of what the filter was built from, and the AND was built from the two sets, not from their intersection.

When most keys are shared #

When the sets overlap heavily the two filters converge. There are only 500 private keys on each side to collide, the AND gains just 140 extra bits, and for absent keys it is within a tenth of the direct filter. The one-sided rate is still four times the direct filter’s, and it is still close to $B$’s own false-positive rate, since $B$ is as full as it was before.

So the AND is a good approximation to a filter of the intersection exactly when there is little outside the intersection — when the combination is nearly unnecessary — and a poor one when the sets are large and the intersection small, which is the case where shipping filters instead of keys saves the most.

Reading the intersection’s size off the bits #

The second use of the AND is to estimate how large the intersection is, and it depends on a formula this collection has already measured.

A Bloom filter with $m$ bits and $k$ hashes that has $X$ bits set holds, in expectation, about

$$\hat n = -\frac{m}{k} \ln\!\left(1 - \frac{X}{m}\right)$$

keys — the inverse of the expected fill, and the same estimate a count read off the leading zeros is compared against as linear counting. Applied to the direct filter’s 1,859 bits it gives almost exactly 500.

Applied to the AND’s 3,232 bits it gives 900. The AND’s bits are the intersection’s bits plus the collisions between the private keys, and the estimate counts every collision bit as evidence of a shared key.

The plate shows the AND’s estimate failing in a specific way. It is not noisy; it is biased, and the bias is roughly constant in absolute terms — six hundred-odd phantom keys at a small intersection, fifty at a large one — because the collisions between private keys depend on how many private keys there are, which falls as the intersection grows. At a true intersection of 100 the estimate is seven times the truth. At 1,500 it is within four per cent.

Inclusion–exclusion works because it never looks at the AND. The OR of two filters is a filter of the union, exactly, so its bit count gives an unbiased estimate of $|A \cup B|$; each filter gives an estimate of its own set’s size; and $|A \cap B| = |A| + |B| - |A \cup B|$. Every term is an estimate from a real filter of a real set, and nothing counts a collision as a member.

That is a general lesson about composing approximate summaries. An operation that is exact on the summaries — OR, for union — yields estimates with known error. An operation that merely resembles the right one — AND, for intersection — yields a summary of something else, and the estimates read from it are estimates of that something else.

The lesson has a counterpart in exact data structures that makes it sharper. A sorted list of keys supports union and intersection equally well, by a merge; a bitmap over a small universe supports both, by OR and AND; neither is lossy, so the two operations are symmetric. A Bloom filter breaks the symmetry because it is a many-to-one summary: many sets map to the same filter, and OR commutes with that mapping while AND does not. The union of two sets maps to the OR of their filters, whichever members they had. The intersection of two sets maps to a filter that depends on which members they had, and the AND of their filters depends only on which bits were set. The occurrences a join invents measures the same asymmetry in a different summary — a join over summarised occurrences that manufactures matches the underlying data never contained — and the mechanism there is the same: a combination applied to summaries that forgot which item produced which mark.

A larger filter narrows the error without removing the bias #

Quadrupling the filters cuts the collisions sharply and the AND’s estimate moves towards the truth, but the shape of the error is the same: a large relative overstatement for a small intersection, shrinking as the intersection grows. Inclusion–exclusion was already accurate and stays accurate.

It is worth noticing what the relative error of the good estimator is doing as well. Inclusion–exclusion subtracts two large estimates to get a small one, so its absolute error is roughly the error of estimating a set of two thousand — a few keys — and its relative error on a small intersection is that absolute error divided by a small number. At a true 100 the estimate of 106 is six per cent out; at a true 10 the same few keys would be most of the answer. And the estimates on the plate are single draws: rerunning with different hash functions moves the inclusion–exclusion estimate by a few keys either way, while it moves the AND’s estimate by about the same few keys around a value that is hundreds too high. The bias is the finding; the noise is small on both. An error measured against the answer is the collection’s account of this: an additive error bound is a guarantee that is good against large answers and useless against small ones, and an intersection is often small.

When to ship filters, and when to ship something else #

The two uses of the AND fail in different ways and deserve different advice.

As a membership filter for the intersection, the AND is safe in the direction that matters most — it never loses a shared key — and its extra false positives are a cost, not a correctness failure. A system that intersects filters to prune candidates before an exact check pays for each false positive with one unnecessary exact check. The measurement says to budget that rate at the larger filter’s own false-positive rate, not at any rate derived from the intersection — 1.8% on this instance, against a direct filter that passed none of the one-sided keys at all.

As an estimate of the intersection’s size, the AND should not be used. Inclusion–exclusion over the same two filters costs one OR and three bit counts, needs no additional state, and is unbiased. The only case it loses is the case every additive estimator loses — a tiny intersection between large sets — and there nothing built from Bloom filters does well.

For that case the right tool is a different summary. Estimating the size of an intersection is estimating a join’s size, and the join order is a guess found that a uniform estimate of a join’s size can be wrong by two orders of magnitude when the heavy values are shared. A sample of each set drawn by the same hash — the smallest $k$ hash values in each — can be intersected directly, and its error is relative to the intersection rather than to the sets. The estimate that is a median of means is the pattern for turning such samples into a bound that holds with stated probability.

What the measurement leaves out #

Both filters have the same size and hash functions. That is required for OR and AND to mean anything, and it is a real constraint on a system: every party must agree on the filter’s parameters before anyone knows how many keys they will hold. A filter sized for one set is the wrong size for another, and the formula everybody sizes filters with measures how wrong the rate gets when a filter’s actual load differs from its planned one.

Two sets, not many. The AND of $r$ filters keeps a bit only if all $r$ have it, which suppresses collisions among private keys — and passes a key in all but one of the sets at that last filter’s rate. The estimate’s bias shrinks with $r$ and the membership error for near-misses does not.

Random keys. Real keys are hashed, and a good hash makes them look random to the filter; the measurement uses keys with no structure, which is what the analysis assumes. A hash is a family, not a function is the reminder that this is an assumption about the hash and not about the keys.

Only Bloom filters. A filter that stores fingerprints of its keys rather than bits — a cuckoo filter, or a quotient filter — can in principle be intersected by comparing fingerprints, and its intersection is a set of fingerprints rather than a pattern of bits. That changes the one-sided error from the other filter’s rate to the chance that two different keys share a fingerprint in the same place, which for fingerprints of a byte or more is far lower. The filter that is allowed to be wrong measured the Bloom filter because it is the simplest and the most widely shipped, and its simplicity is exactly what the intersection loses.

Where this ladder goes next: a filter past its design size #

Every filter on this page held the number of keys it was sized for. The one-sided rate turned out to be set by the other filter’s load, and that raises a question this ladder has not asked directly: what happens to a filter as its load passes the number it was designed for?

The formula predicts a smooth degradation, and a smooth degradation is easy to underestimate. A filter sized for two thousand keys at one per cent holds four thousand at about sixteen per cent and eight thousand at about two in three — nothing breaks, nothing warns, and the filter simply says yes more often until it says yes to almost everything. There is a structure that grows with its data instead, stacking new filters as the old ones fill, each tighter than the last, so that its combined rate stays under a stated bound however many keys arrive. The next rung measures the single filter’s slide and the stack’s bound, and prices the stack’s guarantee in the bits it costs over a filter that had been sized correctly in the first place.