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

Aryan Agarwala, Guy Even

Designs of data structures for approximate membership queries with false-positive errors that support both insertions and deletions stipulate the following two conditions: (1) Dupl…