Shikha Singh, Wellesley College

Abstract

When a large set is stored remotely, membership queries (that is, checking if an element is present in the set) can be expensive. Instead of querying the remote set each time, usually a small in-memory sketch is consulted first to determine “approximate membership”. Bloom filters are one such widely-used approximate-membership query data structures (AMQs). A Bloom filter maintains a compact probabilistic representation of a set S. On a query for an element in S, it guarantees a correct response of "present" but  on a query for an element not in S, it may return "present" with a small false-positive probability ε.

The false-positive probability guarantee ε  of most AMQs holds for a single query or a random query workload. In particular, an adversary who discovers a false positive of a Bloom filter can query it repeatedly driving its false-positive rate to 1.

We say an AMQ is adaptive if it guarantees a false-positive probability of ε for every query, regardless of answers to previous queries. In this talk, I will present upper and lower bounds on adaptive AMQs and show that adaptivity can be achieved at essentially no cost in terms of space or worst-case query time.