A Space Lower Bound for Approximate Membership with Duplicate Insertions or Deletions of Nonelements

Abstract

Designs of data structures for approximate membership queries with false-positive errors that support both insertions and deletions stipulate the following two conditions: (1) Duplicate insertions are prohibited, i.e., it is prohibited to insert an element $x$ if $x$ is currently a member of the dataset. (2) Deletions of nonelements are prohibited, i.e., it is prohibited to delete $x$ if $x$ is not currently a member of the dataset. Under these conditions, the space required for the approximate representation of a datasets of cardinality $n$ with a false-positive probability of $\hat{I}{\mu }^{+}$ is at most $(1+o(1))n\cdot {\log }_2(1/\hat{I}{\mu }^{+})+O(n)$ bits [Bender et al., 2018; Bercea and Even, 2019]. We prove that if these conditions are lifted, then the space required for the approximate representation of datasets of cardinality $n$ from a universe of cardinality $u$ is at least $\frac{1}{2}\cdot (1-\hat{I}{\mu }^{+}-\frac{1}{n})\cdot \log \left(\genfrac{}{}{0ex}{}{u}{n}\right)-O(n)$ bits.