The Bloom Filter Paradox

March 22, 2012
3:00pm-4:00pm
EE Conference Room
Hosted by: Columbia EE/CS Networking Seminar
Speaker: Ori Rottenstreich (Technion - Israel Institute of Technology)

Abstract

Bloom filters and counting Bloom filters (CBFs) are widely used in networking device algorithms. They implement fast set representations to support membership queries with limited error. Unlike Bloom filters, CBFs also support element deletions. In the first part of the talk, we uncover the Bloom paradox in Bloom filters: sometimes, it is better to disregard the query results of Bloom filters, and in fact not to even query them, thus making them useless. We analyze conditions under which the Bloom paradox occurs, and demonstrate that it depends on the a priori probability that a given element belongs to the represented set. In the second part of the talk, we introduce a new general method based on variable increments to improve the efficiency of CBFs and their variants. We demonstrate that this method can always achieve a lower false positive rate and a lower overflow probability bound than CBF in practical systems.

Speaker Biography

Ori Rottenstreich is a Ph.D. student at the Electrical Engineering department of the Technion, Haifa, Israel. His current research interests include exploring novel coding techniques for networking applications.


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