Nine Point Six Bits

A Bloom filter guards an object store lookup. It is sized at m=96m = 96 million bits (12 MB) for n=10n = 10 million keys with k=7k = 7 hash functions, so m/n=9.6m/n = 9.6.

f=(1−e−kn/m)kf = \left(1 - e^{-kn/m}\right)^{k}

The dataset later grows to 40 million keys with the same bit array and the same kk. What is the false positive rate at 10 million keys, and at 40 million?

A

About 1.0 percent, then 100 percent

B

About 1.0 percent, then about 68 percent

C

About 1.0 percent, then about 4.0 percent

D

About 1.0 percent, then about 32 percent