Technical Report CS-2015-04

Title: Counting with TinyTable: Every Bit Counts!
Authors: Gil Einziger and Roy Friedman
PDF - RevisedCS-2015-04.revised.pdf
Abstract: 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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2015
To the main CS technical reports page

Computer science department, Technion