Bloom Filters: the Math
Given n keys, how to choose m and k?
- Suppose m is fixed (ɮn), choose k:
k is optimal when exactly half of the bits are 0
=> optimal k = ln(2) * m/n
- False positive ratio under optimal k is (1/2)k
=> false positive ratio = (1/2)ln2*m/n = (0.62)m/n