False Positive Rate

Published by Mario Oettler on

So far, we learned that bloom filters have a false-positive rate. This rate depends on three parameters:

  1. size of the filter in bit (e.g. 8 bit, 32 bit, 256 bit, etc).
  2. number of hash functions
  3. number of elements included in the bloom filter

We can calculate the probability of a false-positive match with this formula:

Where

  • m: size of the filter in bit
  • k: number of hash functions
  • n: number of elements in the filter
  • p: probability of a false positive match

Numerical Example

Calculate the probability p for a false positive match for the following table:

mknp
1632 
1635 
25635 
256105 
2562005 

Solution

mknp
16320,03309652
16350,238544399
256350,000185372
2561053,14614E-08
25620050,01772303

The following charts show the development of false positives depending on m, k, and n if the other parameters are constant.

False-positive rate depending on k.
False-positive rate depending on m.
False-positive rate depending on n.

Categories: