Columbia University Joint CS/EE Networking Seminar Series

The Bloom Filter Paradox

Ori Rottenstreich

Technion - Israel Institute of Technology

March 22, 3:00-4:00PM EE Conference Room

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.