Bloom filter example

You are going to show the table that results after inserting some keys into a Bloom filter, and then determine the probability of a "false positive on an ensuing membership test.

As with the 2-choice hashing examples, we will assume a universe of 100 possible keys:

\[U = \{1,2,\ldots, 100\}\]

and \(k=2\) so two hash functions:

\[h_1(x) = x \bmod 10\] \[h_2(x) = \left\lfloor\frac{x}{10}\right\rfloor\]

Part 1: Insertions

Insert the following set of keys:

\(\{97, 67, 60, 70\}\)

into a Bloom filter of size 10. Show the table that results.

Part 2: Membership tests

There are 96 possible keys that are not in the set. Assuming that each of them is equally likely to be membership-tested, determine the probability of a "false positive".

So you will want to determine how many of these 96 non-members would incorrectly show as being members of the set, based on the state of the Bloom filter after the insertions. Then divide this number by 96 to get the probability of a false positive.