# Bloom Filters, Adaptivity, and the Dictionary Problem

arXiv: https://arxiv.org/abs/1711.01616 · HTML: https://mlsanity.com/paper/1711.01616/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Nov 2017.

## Built on by (most cited first, 4 of 4)

- [Preventing Verbatim Memorization in Language Models Gives a False Sense of Privacy](https://mlsanity.com/paper/2210.17546/) (2022)
- [Daisy Bloom Filters](https://mlsanity.com/paper/2205.14894/) (2022)
- [Proteus: A Self-Designing Range Filter](https://mlsanity.com/paper/2207.01503/) (2022)
- [Adversarially Robust Bloom Filters: Privacy, Reductions, and Open Problems](https://mlsanity.com/paper/2501.15751/) (2025)

## Abstract (arXiv)

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. An AMQ supports lookups, inserts, and (for some AMQs) deletes. A query for an x in S is guaranteed to return "present." A query for x not in S returns "absent" with probability at least 1-epsilon, where epsilon is a tunable false positive probability. If a query returns "present," but x is not in S, then x is a false positive of the AMQ. Because AMQs have a nonzero probability of false-positives, they require far less space than explicit set representations. AMQs are widely used to speed up dictionaries that are stored remotely (e.g., on disk/across a network). Most AMQs offer weak guarantees on the number of false positives they will return on a sequence of queries. The false-positive probability of epsilon holds only for a single query. It is easy for an adversary to drive an AMQ's false-positive rate towards 1 by simply repeating false positives. This paper shows what it takes to get strong guarantees on the number of false positives. We say that an AMQs is adaptive if it guarantees a false-positive probability of epsilon for every query, regardless of answers to previous queries. First, we prove that it is impossible to build a small adaptive AMQ, even when the AMQ is immediately told whenever it returns a false positive. We then show how to build an adaptive AMQ that partitions its state into a small local component and a larger remote component. In addition to being adaptive, the local component of our AMQ dominates existing AMQs in all regards. It uses optimal space up to lower-order terms and supports queries and updates in worst-case constant time, with high probability. Thus, we show that adaptivity has no cost.