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 76

Static Bloom filter?

Due: March 29
Points: 2

This question is intentionally open-ended. There is not necessarily a single correct answer. You need to show evidence that you understood the material that was presented and can apply it correctly.

Also a caution: Googling "Static Bloom filter" turns up a few results, but as far as I can tell none of them have to do with this problem.

The problem: You are given a set of \(n\) integers, each of which is an integer from 0 up to \(m-1\). You want to construct a data structure to very quickly answer membership test queries on this set: given some integer \(x\), is \(x\) one of the \(n\) integers in the set?

This is the same as the normal set ADT that we have already discussed, except there is no "insert" operation. Hence we say the set is static, meaning the contents of the data structure will never change once it's created.

Describe an idea for an efficient data structure for this static set problem. Your data structure should have \(O(1)\) time for each lookup operation, should use \(O(n)\) space, and should guarantee a small probability of any lookup returning a false positive.