A false-positive rate measures how often a probabilistic membership test says “present” for an item that is absent. Bloom filters accept this error to save memory: a positive lookup may require verification elsewhere, while the metric quantifies the accuracy cost. section 4.12 section 4.10.1
For a Bloom filter, the rate depends on three design quantities:
- m: the number of bits available in the filter. section 4.10
- n: the number of elements inserted, usually estimated from expected workload. section 4.10
- k: the number of independent hash functions used for each key. section 4.10
- Increasing saturation raises the chance that all k positions for an absent key already contain 1 bits; choosing k optimally minimizes the estimated rate for fixed m and n. section 4.10.1
Reading the metric in a layered filter
If each layer has an approximate false-positive ratio PF, a lookup for a key stored c times can incorrectly report c+1 with probability about PF, c+2 with about PF², and c+d with about PF^d. These estimates become less exact when hash-function independence and universality are not guaranteed. section 4.11.3
The rate is therefore a memory–accuracy trade-off, not a defect that Bloom filters can eliminate while retaining the same configuration. When the maximum item count is known, memory can be sized to reach an arbitrarily low target rate; tracking the current rate accurately may require counting unique insertions. section 4.12 section 4.6.7
