Bloom filter — where it appears
Named by 34 essays across 5 fields — each of them below, with the objects they name alongside it.
A filter that is allowed to be wrong
A Bloom filter holding four thousand keys in five thousand bytes answers membership in four memory probes and gets 1.14% of its negative answers wrong. It never gets a positive one wrong. That asymmetry is the whole design, and the rate it makes errors at is a third quantity beside the operation count and the space.
A hash is a family, not a function
Two thousand and forty-eight keys into two hundred and fifty-six buckets. Under a hash that takes the low bits of the key, all 2,048 land in bucket zero and 255 buckets are empty. Under a multiplier drawn at random, the worst bucket holds 11. The keys are the same keys, and they are the multiples of the table size.
The formula everybody sizes filters with
Fill a Bloom filter with four thousand random keys and its measured false-positive rate is within 4% of the textbook formula. Fill the same filter with the integers 1 to 4,000 and the rate is 30% worse than the formula says — not because the hash is bad, but because it is too good on that input.
A floor on the bits
Answering membership for n keys with a false-positive rate of 1% and no false negatives requires at least 6.64 bits per key, whatever the structure. A Bloom filter uses 9.59. The gap is 44.27% at that rate and at every other rate, and it is the first bound on this site that a real structure comes close to.
The evidence a filter cannot remove
A Bloom filter never says no about a key it holds, and that is its whole guarantee. Clear the bits of a thousand deleted keys and it starts saying no about 638 of the thousand it still holds. A counter in every cell repairs it at four times the space; a fingerprint repairs it at twice, and acquires a condition on the caller that neither of the others has.
The intersection two filters cannot report
Two Bloom filters over sets that share five hundred keys, ANDed bit by bit. The result never denies a shared key, and it looks like a filter of the intersection. It is not one — a key in only one of the sets passes it 1.8% of the time where a real filter of the intersection passes none, and reading the intersection's size off its bits gives 900.
The filter each run carries
A log-structured store turns every lookup for a missing key into a read of every level, and a Bloom filter on each run buys those reads back with memory. Spread five bits a key evenly across three levels and a missing key still wastes 0.279 reads. Give the small levels more bits and the large one fewer — the same memory — and it wastes 0.201. At four levels the gap is 0.382 against 0.209, because sized filters stop the waste growing with the number of levels.
A filter past its design size
A Bloom filter sized for two thousand keys at one per cent answers yes to 15.6% of absent keys at four thousand and 68.1% at eight thousand. Nothing fails and nothing warns. A stack of filters that adds a tighter layer whenever the top one fills holds 2.0% at eight thousand, under a bound it can state in advance — in 2.9 times the bits of one filter sized for eight thousand from the start.
A filter that grows by moving a bit
A table of fingerprints can double in place, moving one stored bit of every fingerprint into its slot number, and so grow as one structure with one lookup where a stack of Bloom filters adds layers. Its false-positive rate is fixed by the fingerprint's length and not by the table, so with nothing reserved it doubles as the keys double — 0.69% at a forecast of 2,000, 5.7% at eight times that. Reserve three bits at the start and it holds 0.66% at eight times, in 294,912 bits, exactly what a table built for sixteen thousand keys would hold and fewer than the stack's 428,938. The reserve is a forecast of growth, and past it the rate climbs again.
Two hash values and the keys they copy
A Bloom filter that makes its k bit positions from two hash values, as h₁ + i·h₂, answers yes to 1.6% of absent keys on a 64-bit filter where k independent hashes answer 0.69%. The penalty is not the one expected. With the step forced odd no key ever repeats a bit, while a quarter of independent keys do. What costs the filter is a query whose start and step reproduce a stored key's whole progression, which happens with probability 4n/m², measured to within a few per cent from 64 bits to 4,096. The penalty fades as the filter grows and returns as the hash count rises — 1.13 times at seven positions on 1,024 bits, 5.35 times at thirteen.
The bits given to the wrong keys
A fingerprint table that gives later arrivals longer fingerprints holds 3.6% where a table that reserves nothing holds 21.1%, and it never runs out of reserve because it has none. It also dies at exactly the same size as the table that reserved nothing — 32 times its forecast, on the same key — because every generation shares one quotient, and the generation with the shortest fingerprint is the one that arrived first.
The read a filter has no key for
A Bloom filter on every run of a log-structured store turns a lookup for a missing key from a read of every level into a fraction of one — 0.72 transfers across eight levels at five bits a key, and 0.00027 at twenty. A range query over the same store reads nine transfers at five bits and nine at twenty, because a filter answers whether one named key is in a run and a range has no key to name.
Positions confined to one line
A Bloom filter lookup reads 5.55 cache lines because its six positions are scattered across the whole filter. Confining them to a 512-bit block makes it exactly one, and costs 7% more false positives at eight bits a key. At sixteen bits a key the same block costs 91%, and the two-value trick that is free across a whole filter costs another 135% inside one — because a block is a small filter, and small filters are where the penalty lives.
Two blocks and the chances they add
Send each key to the emptier of two 512-bit blocks and the busiest block of a filter at sixteen bits a key holds 35 keys instead of 51. The false-positive rate gets worse: 0.0997% against 0.0854%. At eight bits a key it nearly doubles. A lookup cannot tell which block a key went to, so it has to ask both, and asking twice is two chances to be wrong. At every density a filter is commonly built at, the repair that tames a hash table's worst bucket buys a filter nothing that a block twice as wide does not.
A block the lookup can work out
Sending each key to the emptier of two blocks flattens the load and doubles the chance of a false positive, because a lookup cannot know which block was chosen. Give each block a threshold on a hash of the key instead and the lookup can work it out: one block read, one chance, and 46% of the load balance kept. At sixteen bits a key that is 0.0618% against one block's 0.0854% and two blocks' 0.0997%. The threshold costs 1.5% of the budget and two bits of it are nearly as good as sixteen.
The runs a range query can skip
A Bloom filter over key prefixes can tell a range query that a run holds nothing it wants, which a filter over keys cannot. On a four-level store of a million keys, a range expected to hold one key costs 4.76 transfers with no such filter and 2.41 with one built on 20-bit prefixes. The best length moves two bits for every tenfold longer range. By a hundred keys the most any range filter could save is a fifth of a transfer, because only the smallest level is ever empty. And the same memory spent on 20-bit prefixes makes a lookup for an absent key three times dearer.
The day a filter cannot grow
A fingerprint table dies when its quotient reaches its shortest fingerprint, and a filter cannot lengthen a fingerprint because it does not keep its keys. The store it filters does. Rebuilt from that store whenever its own count says its rate has passed 1%, a table grown a thousandfold never exceeds 1.05% and ends holding exactly what a reserve of ten bits holds — 18.9 bits a key — having read the store 1.34 times over. The reserve paid its bits early: 34.8 a key at four times the forecast, where the rebuilt table held 18.4. Which one is cheaper depends on whether the growth arrives.
A penalty set by the block
A blocked Bloom filter pays a penalty for its uneven block loads, and a threshold that lets a lookup work out its block repays about a third of it — measured on 2,048 keys, with a prediction that larger filters would widen the gain. From 2,048 keys to 131,072 nothing moves: one block holds 0.086% to 0.090% against a computed 0.086%, and the threshold design 0.060% to 0.065%. The busiest block grows and the rate does not follow it. What sets both the penalty and the repair is the keys a block holds. A threshold turns out to be worth one doubling of the block's width, and its advantage shrinks from 40% at sixteen keys a block to between 5% and 13% at 128.
The small levels' share of a range filter
Prefix filters on a four-level store were proposed a prefix length each, on the reasoning that one length is a compromise between levels whose densities differ 43-fold. Each level does want its own length, 18 to 22 bits, and that recovers a quarter of the gap to a perfect range filter. The gap is mostly not about length. Three fifths of it is false positives. Moving filter bits from the largest level to the small ones — 12, 12, 8 and 3 bits a key instead of 5 each — recovers more than half of it at the same memory, and matches one shared length given twice the memory.
The bits a second threshold costs
A blocked Bloom filter whose first block carries a threshold was proposed a second threshold on each key's second block, with a third block for keys both refuse. It does what it was meant to: at 512-bit blocks it removes nearly a third of the load spread the first threshold left. And the rate does not fall — 0.066% against 0.062% — because the second table, paid for in blocks, raises the rate the filter would have with no spread at all by more than the narrower spread saves. The threshold was stored in more bits than it needs: at four to six bits, one threshold beats the eight-bit design by about a tenth on one run, and a second threshold of the best width ties it at 512-bit blocks.
The resolution a range filter can afford
A prefix filter on each level of a log-structured store answers a range by asking one question for every prefix the range touches, and each can be wrong. A filter holding prefixes at every length from 16 to 24 bits could ask each range at the resolution it needs, and was proposed as the repair. At the store's five bits a key it costs 5.69 transfers a range query where one length a level costs 4.32, because a short range is asked only at the finest length, and that filter now holds a fraction of the memory. Asked at every length it recovers most of that, and seems to overtake the single length at twelve bits a key — but only a single length chosen for five bits. Chosen again for each memory, one length a level beats every multi-resolution design at every memory measured, because the resolution a level can afford is itself set by its memory.
A threshold knows only its own block
A blocked Bloom filter that gives each block a threshold on a hash of the key lets a lookup work out which of two blocks a key went to, and it spends a small table to do it. Sharing one threshold among a group of blocks would shrink the table, and was proposed as the next saving. It is a loss at every group size. With one four-bit threshold a block, 512-bit blocks reach a false-positive rate of 0.061%; shared by a pair, 0.071%; shared by sixteen, 0.100%, worse than no threshold at all. Neighbouring blocks fill at unrelated moments, so a shared threshold closes when the first of its group does, and every key it turns away lands in a second block chosen at random.
One length for the gaps and the clusters
On uniform keys one prefix length a level, chosen for its memory, beat a filter holding every length from 12 to 24 bits. Clustering the keys was predicted to reverse that, because coarse prefixes between clusters are empty and a coarse filter can then say no to a long range in one question. Clustering alone does not: whether ranges fall in the gaps or at the keys, one length re-chosen for that workload still wins, since it moves coarse for the gaps and fine for the keys. The multi-resolution filter wins only where a clustered store is asked both — by 0.17 transfers a query at ten bits a key on sixteen clusters — and it wins on short ranges inside the clusters, not on long ones between them.
Two hashes that shared their low bits
Two pages on blocked Bloom filters with thresholds each recorded an instability they could not explain: a false-positive rate that collapsed on one seed at 256-bit blocks, and a pair of four-bit thresholds measuring 0.169% where its neighbours measured 0.08%. Both came from how a hash was brought into range. Every filter took its block and its ordering value as a modulo of a multiply-shift hash, and the low bits of such a hash depend only on the low bits of the key, so the two values were dependent whenever the block count had a factor of two to spare. At 992 blocks the threshold filter measures anything from 0.185% to 0.645%; read from the hash's top bits, 0.126% to 0.133%.
Two lengths that do the work of eleven
On keys that cluster, asked both between the clusters and at them, a prefix filter holding every length from 12 to 24 bits beat one length a level by 0.17 transfers a range query, and a pair of lengths — one coarse, one fine — was proposed to recover nearly all of that. It recovers more than all of it: 0.23 transfers at ten bits a key, and at four bits, where the eleven lengths lose to one, the pair still saves 0.18. The coarse filter takes under 2% of a level's memory, and the eleven-length filter was leaving its finest length as little as 14% and cannot give it more without starving the lengths its descent passes through. The store predicted to defeat a pair, with gaps at two scales, does not. The saving is bought in questions: the pair asks its filters more often than the eleven lengths do.
A code that has to fit its worst line
A blocked Bloom filter's four-bit thresholds are far from uniform: two blocks in five never close, and the rest crowd into the upper values, an entropy of 2.4 to 2.8 bits. A table coded from that distribution was predicted to match the four-bit rate on under three bits a block. Packed end to end it does, at 2.65 to 3.03 bits, and it costs every lookup a second read for the index. Packed a fixed number to a cache line it needs no index, but every line must hold its worst run of long code words, which costs 3.19 bits at 64-bit blocks and eighty-three code words decoded a lookup. Where the table is large enough for the saving to show, a plain three-bit table gets part of it with none of the costs.
The filter rebuilt with every write
A log-structured store chooses a range filter's two prefix lengths when it writes a level, and a filling store's small levels hold only the keys that arrived last. Choosing at every write was predicted to keep the lead a pair chosen once on the full store has, except where keys arrive a cluster at a time and a small level's choice goes stale when the next batch lands elsewhere. It cannot go stale: a levelled store changes a level's keys only by rewriting it, and rewriting it rebuilds the filter. Choosing at every write and choosing once then differ by at most 2.3% of what a perfect filter saves, on both arrival orders, at two bits a key and at ten, and choosing costs twenty-eight times the hashing. What the order of arrival changes is the store: filled a cluster at a time, its small levels hold one cluster each, and at two bits a key the same filter captures 94% of a perfect filter's saving against 68% shuffled.
One bit a key, divided
A levelled store of a million clustered keys, each level's range filter a pair of prefix lengths chosen when the level is written, captures 68% of a perfect filter's saving at two bits a key spread evenly when its keys arrive shuffled, and 94% when they arrive a cluster at a time. The proposal was to divide the memory by what each level's filter saves per bit, and it predicted the memory would leave the small levels, whose keys the arrival order had already sorted out. It goes the other way, as it did for single prefix lengths, and much further: the small levels take twelve to sixteen bits a key, the deepest level one, and the store captures 99% of a perfect filter's saving on both orders while leaving part of the budget unspent. Divided, one bit a key on average does what four bits spread evenly cannot.
A division chosen before the queries arrive
A levelled store's range-filter memory, divided among its levels by trying every assignment against the store's own queries, captures 99% of a perfect filter's saving on both arrival orders, with the small levels at twelve to sixteen bits a key and the deepest at one. A store writing a level cannot try every assignment, but it knows its levels' sizes, and a rule giving each level δ more bits a key for every factor of four it is smaller was predicted to match the fitted division on the shuffled store and to land near the even split's 94% on the store filled a cluster at a time. It matches the fitted division on both: 97.2% to 99.0% shuffled and 99.7% to 99.9% filled a cluster at a time from one bit a key up, with δ chosen on a sample of queries and charged on others. One δ of four, set before any query, is within a point and a half everywhere from one bit a key up. The rule fails exactly where the proposal said: a δ of six or more at one bit a key gives the deepest level nothing, and the shuffled store falls from 97.2% to 73.9%.
The sizes a store passes through
A levelled store's range-filter memory can be divided by its levels' sizes alone, a few more bits a key for every factor of four a level is smaller than the deepest, and on the full store that rule matched the division fitted to the store's own queries at every budget. Through the fill it does not. At a bit a key or less it falls up to 17 points of a perfect filter's saving behind on the shuffled store and 26 on the store filled a cluster at a time, and every large loss has the same cause: part way through the fill the deepest level is a smaller share of the store, and the rule gives it nothing.
A floor under every level
A levelled store's filter memory divided by its levels' sizes lost up to 26 points of a perfect filter's saving part way through its fill, every large loss a level given no filter at all. A floor of half a bit a key under every level was predicted to close every gap above five points at one bit a key and cost nothing at two and four. It closes them: the worst gap at one bit falls from 17 points to 4 on the shuffled store and from 25 to under 1 on the clustered one, and nothing moves at two bits and up. At half a bit a key the floor is the whole budget and the rule becomes the even split, which the clustered store wants half way through and the shuffled store, at the same sizes, loses 35 points by.
A span the queries do not see
A rule for dividing a levelled store's range-filter memory by its levels' sizes, with a floor of half a bit a key, came within five points of the division fitted to the store's own queries at every budget from one bit up — but at half a bit the shuffled and the clustered store wanted opposite divisions of identically sized levels. A level's fences, its first and last keys, say how much of the key space it spans, and a clustered level spans little. Scaling each level's bits by that span was predicted to close the half-bit gap and change nothing above. It changes nothing at half a bit — where the floor is the whole budget, so there is nothing left to scale — and from one bit up it puts the clustered store 30 points behind the fitted division, where the floored rule was within one. A level holding one cluster spans 0.4% of the key space and meets 4.4% of the queries, because half of them start at a stored key: the fences measure the key space, and the queries are aimed at the keys.
The lookups a filter turns away
A capped cuckoo table keeps its stopped keys in an overflow block a region, and at 95% load every lookup for an absent key reads those blocks — 1.93 of them, because a key could have been stopped in either of its buckets' regions. A Bloom filter over each region's overflow at eight bits a key was predicted to let about 2% of those lookups through. It lets 2.07% through, and the prediction was right for two wrong reasons that cancel. Filing every stopped key under its first bucket halves the rest, and then the lookups the filter cannot help, the 3.9% of keys that really live in the overflow, are what is left to pay.
The block already open
A cuckoo table that caps its kick chain at two keeps the keys it stopped in an overflow block a region, and with a filter in front of each block a successful lookup's cost is set by the share of keys living there: 3.7% after one fill to 95%. Under deletions and insertions in equal numbers it was predicted to climb without limit unless every deletion moved a stopped key home. It does not climb without limit; it settles, at 9.2%. Homing at every deletion holds it at 4.0%, as predicted — by reading a block on 98% of deletions, and by sending a quarter of the insertions that follow to the overflow, because a key moved home takes the slot the next key needed. Moving keys home only when their block is already open for another reason holds the overflow at 4.9% for 0.07 blocks a pair more than leaving keys alone, and costs less than leaving keys where they stopped from one and a half successful lookups a deletion.
Named alongside it
The objects these essays reach for when they reach for this one.
Design parameterFalse-positive rateLsm treePer levelRange queryRead amplificationBlocked filterSpace time tradeApproximate membershipBlock transferLoad factorSpace accounting