Counting with TinyTable: Every Bit Counts!

Counting Bloom filters (CBF) and their variants are data structures that support membership or multiplicity queries with a low probabilistic error. Yet, they incur a significant memory space overhead when compared to lower bounds as well as to (plain) Bloom filters, which can only represent set membership without removals. This work presents TinyTable, an efficient hash table based construction that supports membership queries, multiplicity queries (statistics) and removals. TinyTable is more space efficient than existing alternatives, both those derived from Bloom filters and other hash table based schemes. In fact, when the required false positive rate is smaller than 1 %, it is even more space efficient than (plain) Bloom filters.