Counting with TinyTable: Every Bit Counts!

October 13, 2015
EE Conference Room (Mudd 1300)
Speaker: Prof. Roy Friedman, Computer Science, Technion


Counting Bloom filters (CBF) and their variants are data structures that support membership or multiplicity queries with a low probabilistic error. Their applications include flow monitoring, anomaly detection, load balancing, caching, natural language processing and database optimization. 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.

In this talk, I will present 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 incurs acceptable runtime overheads.

* Joint work with Gil Einziger

Speaker Bio

Roy Friedman is an associate professor in the department of Computer Science at the Technion - Israel Institute of Technology. His research interests include Distributed Systems with emphasis on Fault-Tolerance, Dependability, High Availability, Consistency, Mobile Computing, Mobile Ad-Hoc Networks, and Peer-to-Peer computing. Roy Friedman served as PC co-chair for ACM DEBS, ACM SYSTOR and Autonomics as well as vice chair for IEEE ICDCS and EuroPar, and fast abstract chair for IEEE DSN. He is also an associate editor for IEEE TDSC. Formerly, Roy Friedman was an academic specialist at INRIA (France) and a researcher at Cornell University (USA). He is a founder of PolyServe Inc. (acquired by HP) and holds a Ph.D. and a B.Sc. from the Technion.

500 W. 120th St., Mudd 1310, New York, NY 10027    212-854-3105               
©2014 Columbia University