Question

The Bloom Filter has reasonably accurate computation for the false positive rate pkpk, assuming the kk hash functions are uniformly random is

pk=12×(1−(1−1m)kn)kpk=12×(1−(1−1m)kn)k

where nn is the number of values already added.

Also, the literature suggests trying to ensure  (1−(1−1m)kn)(1−(1−1m)kn) is close to 1/2.

Suppose you inserted 211,422 words into a Bloom Filter with 3 hash functions, and you will be searching 2,135 words.

By setting the size of the Bloom Filter to be 1,120,000 bits or 131,250 bytes, the false positive rate for the word list will be smaller than 10%

Select one:

True

False

Answer 1

The answer is True.

If you are sure in prior that you wanted the false positive rate (FP rate %) to be
smaller than some small value, then, the number of elements 'n' to be inserted can be determined based on k and m.

Ensure that (1 - (1-1/m)
kn) is constant which is close to 1/2.

In order to ensure a false positive rate (FP rate) of smaller than 10% (percentage) in a word list, please make sure to assign 'm' to at least 1,120,000 or 131,250 bytes.