Bloom Filters, Adaptivity, and the Dictionary Problem

Michael A. Bender, Martin Farach-Colton, Mayank Goswami +3

The Bloom filter---or, more generally, an approximate membership query data structure (AMQ)---maintains a compact, probabilistic representation of a set S of keys from a universe U…