Gil Einziger

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 algorithm that supports membership queries, removals and multiplicity queries (statistics). TinyTable improves space efficiency by as much as 28% compared to CBF variants and as much as 60% for monitoring flow statistics. When the required false positive rate is smaller than 1%, TinyTable is even slightly more space efficient than (plain) Bloom filters. Our performance study shows that TinyTable has acceptable runtime overheads.