COMPUTER SCIENCE COLLOQUIUM

Ready, Set, Approximate!

Rasmus Pagh Theory Department IT University of Copenhagen

Tuesday, December 7, 2004, at 14:15 Seminar Room

ABSTRACT

The talk 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. The talk presents 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 deletions on S in amortized expected constant time.

Host: Joan Boyar

---

SDU HOME | IMADA HOME | Previous Page

---

Last modified: October 27, 2004.

Joan Boyar (joan@imada.sdu.dk)