Dynamic Dictionaries for Multisets and Counting Filters with Constant Time Operations.

We resolve the open problem posed by Arbitman, Naor, and Segev [FOCS 2010] of designing a dynamic dictionary for multisets in the following setting: (1) The dictionary supports multiplicity queries and allows insertions and deletions to the multiset. (2) The dictionary is designed to support multisets of cardinality at most n (i.e., including multiplicities). (3) The space required for the dictionary is \((1+o(1))\cdot n\log \frac{u}{n} + \varTheta (n)\) bits, where u denotes the cardinality of the universe of the elements. This space is \(1+o(1)\) times the information-theoretic lower bound for static dictionaries over multisets of cardinality n if \(u=\omega (n)\). (4) All operations are completed in constant time in the worst case with high probability in the word RAM model.