Computer Science, Technion
Mon. Oct. 12, 2:30pm
EE conf. room (Mudd 1300)
Abstract:
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
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.