Skip to Main content Skip to Navigation
Journal articles

Improving Retouched Bloom Filter for Trading off Selected False Positives Against False Negatives

Abstract : Where distributed agents must share voluminous set membership information, Bloom filters 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 transmission 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 filter 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.
Document type :
Journal articles
Complete list of metadata
Contributor : Timur Friedman Connect in order to contact the contributor
Submitted on : Tuesday, June 11, 2013 - 4:45:16 PM
Last modification on : Sunday, June 26, 2022 - 9:58:47 AM

Links full text



Benoit Donnet, Bruno Baynat, Timur Friedman. Improving Retouched Bloom Filter for Trading off Selected False Positives Against False Negatives. Computer Networks, Elsevier, 2010, 54 (18), pp.3373--3387. ⟨10.1016/j.comnet.2010.07.003⟩. ⟨hal-00832981⟩



Record views