Precision measures how reliably positive membership results identify elements actually present in a represented set. For Bloom filters, it is evaluated through the probability or ratio of false positives. section 4.12 section 4.10
A Bloom filter’s precision depends on the number of bits in its buffer (m), the number of stored elements (n), and the number of independent hash functions (k). Under universal-hashing assumptions, these variables estimate the false-positive probability after n insertions. section 4.10 section 4.10.1
Use the parameters to make the memory–accuracy trade-off explicit:
- Treat n as the expected or conservatively estimated number of stored elements. section 4.10
- Choose m within the available memory budget. section 4.10
- Tune k to minimize false positives and obtain optimal precision for the chosen m and n. section 4.10 section 4.10.1
Tracking URLs
A crawler can use a Bloom filter to track URLs it has encountered. Estimating precision helps predict how often a membership test may incorrectly report that an unseen URL was already stored, while the expected request volume and memory budget guide m and k. section 4.12 section 4.10
