Space Lower Bounds for Dynamic Filters and Value-Dynamic Retrieval

A filter is a data structure that answers approximate-membership queries on a set S of n elements, with a false-positive rate of є. A filter is said to be dynamic if it supports insertions/deletions to the set S, subject to a capacity constraint of n. This paper considers the space requirement of filters, regardless of running time. It has been known for decades that static filters have optimal space n logє−1 + O(1) expected bits, and that dynamic filters can be implemented in space n logє−1 + Θ(n) bits. We prove that this Θ(n)-bit gap is fundamental: any dynamic filter must use n logє−1 + Ω(n) bits, no matter the choice of є. Extending our techniques, we are also able to obtain a lower bound for the value-dynamic retrieval problem. Here again, we show that there is a Θ(n)-bit gap between the optimal static and (value-)dynamic solutions.