Broken Bloom Filters

Computer Science Level 4

A bloom filter is composed of a bit array of $2^{16}$ bits. We are told that the filter is designed to be optimally performing when there are $2^8$ entries.

Given that the filter is filled with $2^8$ entries, what is the expected number of queries one has to perform to perform to get a false positive?

If your answer is $x$ , enter the value of $\lfloor \log_{10} x \rfloor$ .

Notation : $\lfloor \cdot \rfloor$ denotes the floor function .

The answer is 53.

1 solution

Abhishek Sinha
Jul 12, 2016

Substituting for the optimal $k=k^*$ probability of a false positive is $\approx 2^{-k^*}$ . Hence we need $2^{k^*}$ insertion in expectation to get a false positive. Now from the formula, we have $k^*= \ln(2)2^8$ and the answer may be readily computed.

how do we get the FP 2^k ? any formula to calculate it?

p w - 2 years, 4 months ago

Broken Bloom Filters

The answer is 53.

1 solution

0 pending reports