Problem 82

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

Static Bloom filter?

Due: April 19
Points: 3

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.