This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Problem 75

Bloom filter example

Due: March 29
Points: 2

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.