Reference : Improving Retouched Bloom Filter for Trading Off Selected False Positives Against Fal...
Scientific journals : Article
Engineering, computing & technology : Computer science
Improving Retouched Bloom Filter for Trading Off Selected False Positives Against False Negatives
Donnet, Benoît mailto [Université Catholique de Louvain - UCL > ICTEAM > INL > >]
Baynat, Bruno [> > > >]
Friedman, Timur [> > > >]
Computer Networks
Elsevier Science
Yes (verified by ORBi)
The Netherlands
[en] Bloom filter ; Retouched Bloom filter ; false negative
[en] Where distributed agents must share voluminous set membership information, Bloom fil- ters provide a compact, though lossy, way for them to do so. Numerous recent networking papers have examined the trade-offs between the bandwidth consumed by the transmis- sion of Bloom filters, and the error rate, which takes the form of false positives. This paper is about the retouched Bloom filter (RBF). An RBF is an extension that makes the Bloom fil- ter more flexible by permitting the removal of false positives, at the expense of introducing false negatives, and that allows a controlled trade-off between the two. We analytically show that creating RBFs through a random process decreases the false positive rate in the same proportion as the false negative rate that is generated. We further provide some simple heuristics that decrease the false positive rate more than the corresponding increase in the false negative rate, when creating RBFs. These heuristics are more effective than the ones we have presented in prior work. We further demonstrate the advantages of an RBF over a Bloom filter in a distributed network topology measurement application. We finally discuss several networking applications that could benefit from RBFs instead of standard Bloom filters.

File(s) associated to this reference

Fulltext file(s):

Open access
sdarticle.pdfPublisher postprint754.9 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.