Space Lower Bounds for Dynamic Filters and Value-Dynamic Retrieval

A filter is a data structure that answers approximate-membership queries on a set of elements, with a false-positive rate of . A filter is said to be dynamic if it supports insertions/deletions to the set , subject to a capacity constraint of .

This paper considers the space requirement of filters, regardless of running time. It has been known for decades that static filters have optimal space log -1 + (1) expected bits, and that dynamic filters can be implemented in space log -1 + Θ( ) bits. We prove that this Θ( )-bit gap is fundamental: any dynamic filter must use log -1 + Ω( ) 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 Θ( )-bit gap between the optimal static and (value-)dynamic solutions.

• Theory of computation → Data structures design and analysis; Cell probe models and lower bounds.