On the Analysis and Impact of False Rates of Bloom Filters in Distributed Systems, in Proceedings of the 35th International Conference on Parallel Processing (ICPP), Columbus, pp. 255-262, OH, August, 2006 (Acceptance rate: 64/200 = 32%).
Abstract
Recently, Bloom filters have been widely used in distributed systems where they are replicated to process distributed queries. Bloom filter replicas become stale in a dynamic environment. A good understanding of the impact of staleness on false negatives and false positives can provide the system designers with important insights into the development and deployment of distributed Bloom filters in many distributed systems. To our best knowledge, this paper is the first one that analyzes the probabilities of false negatives and positives by developing analytical models, which take the staleness into consideration. Based on the theoretical analysis, we proposed an updating protocol that directly control the false rate. Extensive simulations validate the analytical models and prove the updating protocol to be very accurate and effective.
BibTeX Entry
	@inproceedings{zhu_icpp06, author = {Yifeng Zhu and Hong Jiang}, title = {False Rate Analysis of {B}loom Filter Replicas in Distributed Systems}, booktitle = {ICPP '06: Proceedings of the 2006 International Conference on Parallel Processing}, year = {2006}, isbn = {0-7695-2636-5}, pages = {255--262}, publisher = {IEEE Computer Society}, address = {Washington, DC, USA}, }
Full Paper
pdf
Last modified on October 16, 2007