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.
Type de document :
Article dans une revue
Computer Networks, Elsevier, 2010, 54 (18), pp.3373--3387. 〈10.1016/j.comnet.2010.07.003〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00832981
Contributeur : Timur Friedman <>
Soumis le : mardi 11 juin 2013 - 16:45:16
Dernière modification le : mercredi 21 mars 2018 - 18:57:58

Lien texte intégral

Identifiants

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

170