Presenter: Ori Rottenstreich (Princeton)
Title: A Novel Approach to Bloom Filters
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 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. In the second 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.
Bio: Ori Rottenstreich is a Postdoctoral Research Fellow at the department of Computer Science, Princeton university, working with Prof. Jennifer Rexford. He received the Ph.D. degree from the Electrical Engineering department of the Technion, Haifa, Israel in 2014. He is a recipient of the Rothschild Yad-Hanadiv postdoctoral fellowship, the Google Europe PhD Fellowship in Computer Networking and the best paper runner up award at the IEEE Infocom 2013 conference.
