bloom filter

Bloom Filter

m=|bit array|, n=|S|, k=# of hash functions.

false positive=

Given m and n,  will results the minimum false positive. k=-log₂eps.

y=D(expression((1-exp(c*x))^x),'x')

> y

(1 - exp(c * x))^x * log((1 - exp(c * x))) - (1 - exp(c * x))^(x -     1) * (x * (exp(c * x) * c))

let y=0, we get k

let c=m/n, number of bits of each S_i

 

in code: given eps and n, we get k=-log₂eps, c=k/ln2, m=n/c

 Java code :

https://github.com/MagnusS/Java-BloomFilter/blob/master/src/com/skjegstad/utils/BloomfilterBenchmark.java