Mitigating False Positives in Filters: to Adapt or to Cache?
Michael A. Bender, Rathish Das, Martı́n Farach-Colton, Tianchi Mo, David Tench, Yung Ping Wang · Society for Industrial and Applied Mathematics eBooks · 2021
A filter is adaptive if it achieves a false positive rate of ∊ on each query independently of the answers to previous queries. Many popular filters such as Bloom filters are not adaptive—an adversary could repeat a false-positive query many times to drive the false-positive rate to 1. Bender et al. [4] formalized the definition of adaptivity and gave a provably adaptive filter, the broom filter. Mitzenmacher et al. [20] gave a filter that achieves a lower empirical false-positive rate by exploiting repetitions. We prove that an adaptive filter has a lower false-positive rate when the adversary is stochastic. Specifically, we analyze the broom filter against queries drawn from a Zipfian distribution. We validate our analysis empirically by showing that the broom filter achieves a low false-positive rate on both network traces and synthetic datasets, even when compared to a regular filter augmented with a cache for storing frequently queried items.