The Bloom paradox: When not to use a Bloom filter?
Authors:
- 1 March 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1638-1646
Abstract
In this paper, 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 first analyze conditions under which the Bloom paradox occurs in a Bloom filter, and demonstrate that it depends on the a priori probability that a given element belongs to the represented set. We show that the Bloom paradox also applies to Counting Bloom Filters (CBFs), and depends on the product of the hashed counters of each element. In addition, both for Bloom filters and CBFs, we suggest improved architectures that deal with the Bloom paradox. We also provide fundamental memory lower bounds required to support element queries with limited false-positive and false-negative rates. Last, using simulations, we verify our theoretical results, and show that our improved schemes can lead to a significant improvement in the performance of Bloom filters and CBFs.Keywords
This publication has 13 references indexed in Scilit:
- The Bloom paradox: When not to use a Bloom filter?2012
- A Generalized Bloom Filter to Secure Distributed Network ApplicationsComputer Networks, 2011
- Design exploration of hybrid caches with disparate memory technologiesACM Transactions on Architecture and Code Optimization, 2010
- Designing Packet Buffers for Router LinecardsIEEE/ACM Transactions on Networking, 2008
- Retouched bloom filters2006
- Lossy DictionariesLecture Notes in Computer Science, 2001
- Two Observations on Probabilistic Primality Testing2000
- Summary cache: a scalable wide-area Web cache sharing protocolIEEE/ACM Transactions on Networking, 2000
- Exact and approximate membership testers1978
- Space/time trade-offs in hash coding with allowable errorsCommunications of the ACM, 1970