Lecture Notes: Bloom Filter

Let U be the set of integers {1,..., U}, and S of a subset of U with size n ( ≤ U). We want to preprocess S into a structure so that, given any integer q ∈ U, we can determine quickly whether q ∈ S. We will refer to this problem as the membership problem. We represent each integer in U with w = logU bits (all logarithms have base 2 by default). A simple solution is to build a hash table on S which answers a query in constant time (which can be made worst-case using perfect hashing). The space of the hash table is O(nw) bits. In this lecture, we ask the question: is it possible to solve the problem using a structure of o(nw) bits? The answer is negative if a precise answer is always desired – it is easy to show that any structure for this purpose requires at least lo