A compact filter, not an exact set
Definition 6.1.1
(Bloom filter, false positive and false negative)
A Bloom filter has bits, initially zero, and stable hash functions taking keys to indices . Inserting a key sets each indicated bit to one; a query says definitely absent if any indicated bit is zero and possibly present otherwise. Hash outputs may repeat. The filter does not retain the keys and cannot list them or certify that a positive answer is correct. A false positive is a "possibly present" answer for a key that was not inserted; a false negative is a "definitely absent" answer for a key that was inserted.
Theorem 6.1.2
(No false negatives for inserted keys)
With stable hash functions, an initially empty filter and no clearing of bits, every inserted key is answered "possibly present" by every later query.
Proof
(Bits are only ever set)
Let be inserted. At that moment, all bits become one. Later operations are insertions, which only set bits, and queries, which change nothing. Since the functions are stable, a later query for reads the same positions, and finds each of them equal to one. So it never answers "definitely absent".
A noninserted key can still find all its bits set by other keys: that is a false positive. A positive answer should be checked in an exact backing store when exact membership is required.
A trace and an unsafe deletion
Worked example 6.1.3
(Two insertions, one false positive and one certain absence)
Take , with the following prescribed hash outputs for four distinct keys. These are example outputs, not a claim about a particular hash-function implementation.
| Key | ||
|---|---|---|
| a | 1 | 5 |
| b | 2 | 5 |
| c | 1 | 2 |
| d | 0 | 5 |
Insert only a and b. The set bits are . Query c returns possibly present, although c was not inserted; query d returns definitely absent because bit is zero. The false positive did not require the hash pairs for c and an inserted key to be identical.
Counterexample mode
Clearing shared bits breaks the guarantee
Suppose we try to delete a by clearing bits and . Key b is still stored in the intended set but needs bit , so its next query reports definitely absent. A plain bit array does not record which keys share a bit. A counting variant can support deletion only with its own counter, overflow and valid-deletion rules; those rules are not established by this filter.
Common mistake
(Treating a positive answer as proof of membership)
In the trace above, query c answers possibly present, yet c was never inserted: bits and were set by a and b. Only the answer "definitely absent" is a certain statement about the inserted set. A positive answer is certain only after an exact check against stored keys.
What a probability calculation assumes
A deterministic list of bit positions has no intrinsic probability. For a probability model, fix the inserted keys and an absent query independently of the random hash choices. Suppose every hash output used for those distinct keys is independent and uniform on the indices, including outputs of different functions. This idealized model is stronger than merely saying each hash is individually uniform.
Theorem 6.1.4
(False-positive probability in the uniform model)
Under this model, after distinct insertions let be the random number of one-bits. For an absent query key, the false-positive probability satisfies
Proof
(Conditioning on the completed bit array)
Conditional on the completed bit array, the absent query's outputs are independent and uniform, because they are independent of the insertion outputs that determined the array. Each lands on a one-bit with probability , so all do with probability . Taking the expectation over the array gives the first identity.
For the second, a fixed bit stays zero exactly when none of the insertion outputs equals its index, which has probability . So the bit is one with probability , and summing over the bits and using linearity of expectation gives . For the array is all zero, and .
Proof X-ray
Where independence is spent
Independence of the query's outputs from the insertion outputs is used once, when the conditional probability is written as ; without it the query could be correlated with the filter's contents and the factor would be wrong. Independence among the query outputs is used again to take a th power. The expectation of uses the independence of the insertion outputs in the zero-bit calculation, but only linearity of expectation across the bits, not independence between different bits. The two identities answer different questions: the first gives the exact probability, the second only the mean occupancy.
Substituting the mean into the th power gives a common approximation, not generally the exact expectation of the power. The model and any approximation must be checked against the actual implementation and workload.
Common mistake
(Replacing the occupancy by its mean inside the power)
Let , and insert one fixed key. Its two independent uniform outputs agree with probability , yielding ; otherwise . For an independent absent query,
Here , but its square is , not . The occupancy is random, so the power of its mean cannot simply replace the mean of its power.
Worked example 6.1.5
(Mean-based estimate against the exact value for m = 8, k = 2, n = 2)
There are insertion outputs. A fixed bit is zero with probability , so a bit is one with probability , and the mean-based estimate is . For the exact value, let the query outputs be . If (probability ), both land on a one-bit with probability . If (probability ), the probability that both bits are one is , by excluding the cases where either bit stays zero. Hence
The estimate differs from the exact value , as the case above also showed. The same formula for gives , because no bit is set.
Exercises with solutions
Quick check
(Repeated insertion. What happens to the bit array if the same key is inserted twice with stable hashes?)
Which bits does the second insertion set?
Solution · Answer
The second insertion sets the same bits again; the array is unchanged.
Quick check
(A negative query. In the trace, why is d definitely absent?)
Which bit does d require that nobody set?
Solution · Answer
Its required bit is zero, and every inserted key would have set all its required bits.
Quick check
(The tiny model. In the model, what is ?)
When do the two insertion outputs differ?
Solution · Answer
, because the two insertion outputs differ in two of four equally likely ordered pairs.
Quick check
(An exact store. Can a Bloom filter replace a set when an incorrect positive answer is unacceptable?)
What can a positive answer guarantee?
Solution · Answer
Not by itself. A positive may be false, so an exact verification step or a different structure is needed.