A Bloom filter stores a set in m bits by hashing each key to k of them and setting those bits. A clear bit is a certain no; a set bit may be somebody else's. The false-positive rate is (1 − (1 − 1/m)^{kn})^k exactly, and at sixteen keys in 160 bits with seven hashes that is 0.008319. The textbook (1 − e^{−kn/m})^k gives 0.008194, and the gap between the two is the independence assumption.
Core ideas
The hard idea is that one answer is certain and the other is not. The other two are the exact rate and the idealisation that is usually quoted in its place.
Inserting x sets k specific bits. So if any of x's k bits is clear, x was never inserted — a certain no, with no probability attached. If all k are set, either x is present or other keys happened to set all k between them. The error is one-sided, and it is the same shape as the primality test's: one answer is a proof and the other is silence.
A given bit is left clear by all kn settings with probability (1 − 1/m)^{kn}, so it is set with probability 1 − (1 − 1/m)^{kn}, and a false positive needs k such bits: (1 − (1 − 1/m)^{kn})^k. That is a rational number, and at m = 160, n = 16 and k = 7 its denominator has over seventeen hundred digits. A double turns it into NaN; the lab holds it as BigInt over BigInt and prints the decimal by long division.
(1 − e^{−kn/m})^k is what textbooks quote, and it is the exact expression with two idealisations: (1 − 1/m)^{kn} ≈ e^{−kn/m}, and the k bit tests treated as independent when they are not. It reads 0.008194 where the truth is 0.008319. The panel prints both and the difference, and the giveaway is that the idealised figure depends only on k and the bits per key — move the key slider and it does not change at all, while the exact rate does.
The material
The structure, the exact rate, the idealisation beside it, the best k found by scanning, and the operation the filter cannot support.
A Bloom filter for a set is an array of m bits, initially all clear, together with k hash functions into 0..m − 1. To insert x, set the bits h₁(x), …, hₖ(x). To query x, report present if all k of those bits are set and absent otherwise. The structure stores no keys.
That last sentence is the point of it. Sixteen keys at ten bits each is 160 bits — twenty bytes — for a set that would take at least sixteen machine words to store exactly. The saving is what the false-positive rate is paid for, and the rate is what this lesson computes.
Suppose n keys have been inserted into m bits with k hash functions, each of the kn settings choosing a bit uniformly at random and independently. Then a key that was never inserted is reported present with probability (1 − (1 − 1/m)^{kn})^k.
Fix a bit. Each of the kn settings misses it with probability 1 − 1/m, and the settings are independent, so the bit is clear with probability (1 − 1/m)^{kn} and set with probability 1 − (1 − 1/m)^{kn}.
A query on an absent key reports present exactly when all k of its bits are set. Treating those k events as independent gives the product, which is the k-th power.
□
The second step is where the honesty is required. The k bits of a query are not independent: knowing that one of them is set is mild evidence that the filter is full, which makes the others more likely to be set too. So the expression above is itself an idealisation of the truth for a real filter, and this library's arithmetic computes it exactly as the expression it is, while labelling the further e^{−kn/m} step as approximate. The lab's measured column — the false positives an actual filter returned — is the only figure on the page with no model in it.
m = 160, n = 16, k = 7. The exact rate is 0.008319, which the panel also prints as about 1 in 120. The idealised (1 − e^{−kn/m})^k gives 0.008194, a difference of 1.25 × 10⁻⁴. The filter the lab built set 74 of its 160 bits and returned 1 false positive in 200 queries of keys it had never seen.
Three numbers again, in the shape this course has used throughout. 0.008319 is exact under the stated model. 0.008194 is an approximation of it and is labelled. 1 of 200 is a measurement on one filter with one seed, and 200 queries cannot resolve a rate of one in 120 — the expected number of false positives in 200 queries is about 1.66, so 1 is unremarkable and so would 0 or 4 be.
More hash functions set more bits, which raises the chance that any given bit is set, and they also require more bits to be set for a false positive, which lowers it. The two effects compete and there is an optimum. The usual rule is k* = (m/n)·ln 2, which at ten bits per key suggests 6.93. The panel does not use it: it evaluates the exact rate at every k from 1 to 10 and reports the smallest.
The curve is flat near its minimum — k = 6, 7 and 8 are within four per cent of each other — and it climbs sharply on the left. So under-hashing is expensive and over-hashing is cheap, which is worth knowing when the rule of thumb lands between two integers. At twelve keys and twelve bits each the panel's scan puts the optimum at k = 8 with a rate of 0.003204, and a filter running at k = 10 there pays 0.003414 — six per cent worse for 25 per cent more work.
A Bloom filter cannot delete. Clearing the k bits of a removed key would clear bits that other keys had set, and those keys would then be reported absent — a false negative, which is the one answer the structure exists never to give. The one-sided error is the whole guarantee, and deletion would destroy it rather than degrade it.
That is also why the structure is used where a certain no is what matters: a cheap pre-filter in front of an expensive lookup. Storage Engines and Indexes, on the System Design path, puts one in front of a disk read for exactly that reason, and the consequence of a false positive there is a wasted read rather than a wrong answer.
The rate is a design parameter and it is computable in advance, which is the unusual thing about this structure. Choose the bits per key and k and the false-positive rate follows exactly; there is no measurement to run and no instance-dependence to worry about. What must not happen is quoting the idealised figure as the rate when the exact one is available, or quoting either without saying which.
Interactive
A clear bit is a certain no; the false-positive rate is a fraction
Method
Pick the bits per key first; it is the parameter the rate really depends on.
The idealised rate depends only on k and m/n, so the bits per key is the budget and k is the tuning. Ten bits a key with the best k gives about one false positive in 120; eight bits a key gives about one in 46.
(m/n)·ln 2 lands between integers and rounds in an unstated direction. The panel evaluates every k exactly, and the curve is flat near the optimum and steep to the left of it, so a guess that is too small costs much more than one that is too large.
0.008319 and 0.008194 are different numbers and only the first is the expression this model gives. If the idealisation is what you have, label it; the panel prints the difference in its own row so the size of the concession is visible.
It would not be, which is why deletion does not exist. If your use needs removal, a Bloom filter is the wrong structure and a counting variant is a different structure with a different analysis.
The idealisation depends only on k and the bits per key; the exact rate depends on the actual filter. Here is what that difference looks like when the bits per key are held fixed and the filter grows.
The idealised column is the same number twice, because kn/m is 0.7 in both rows. The exact column is not: the smaller filter is genuinely worse, at 0.008319 against 0.008214, because (1 − 1/m)^{kn} and e^{−kn/m} diverge more when m is small. So the approximation hides a real difference between two filters, and it hides it in the direction of optimism.
Both exact figures sit above the idealisation, which is the general pattern here and is worth knowing: the idealisation is optimistic. Quoting it as the rate understates the false-positive rate you will actually see, by a quarter of a per cent at a thousand bits and by one and a half per cent at 160.
For a faded rehearsal, drop the bits per key to eight and predict what happens to the best k before the panel redraws. The supplied first move is this: the rule of thumb is (m/n)·ln 2, so at eight bits it suggests about 5.5. Say which integer the exact scan will choose, then check — and then say why the rate at that k is nearly three times the ten-bit rate when the space only fell by a fifth.
You should be able to derive (1 − (1 − 1/m)^{kn})^k, name the idealisation that turns it into the textbook formula and say which direction the error goes, choose k by scanning rather than rounding, and explain why deletion is not available.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.