An Optimal Bloom Filter Replacementh∗

This paper considers space-efficient data structures for storing an approximation S ′ to a set S such that S ⊆ S′ and any element not in S belongs to S ′ with probability at most . The Bloom filter data structure, solving this problem, has found widespread use. Our main result is a new RAM data structure that improves Bloom filters in several ways: • The time for looking up an element in S ′ is O(1), independent of . • The space usage is within a lower order term of the lower bound. • The data structure uses explicit hash function families. • The data structure supports insertions and dele-tions on S in amortized expected constant time. The main technical ingredient is a succinct representa-tion of dynamic multisets. We also consider three recent generalizations of Bloom filters.