Paper published in a book (Scientific congresses and symposiums)
Retouched Bloom Filters: Allowing Networked Applications to Flexibly Trade Off False Positives Against False Negatives
Donnet, Benoît; Baynat, Bruno; Friedman, Timur
2006In ACM CoNEXT
Peer reviewed
 

Files


Full Text
rbf.pdf
Publisher postprint (450.59 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Bloom filters; Retouched bloom filters; false negative
Abstract :
[en] Where distributed agents must share voluminous set mem- bership 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 er- ror rate, which takes the form of false positives, and which rises the more the filters are compressed. In this paper, we introduce the retouched Bloom filter (RBF), an extension that makes the Bloom filter more flexible by permitting the removal of selected false positives at the expense of gen- erating random false negatives. We analytically show that RBFs created through a random process maintain an overall error rate, expressed as a combination of the false positive rate and the false negative rate, that is equal to the false positive rate of the corresponding Bloom filters. We further provide some simple heuristics that decrease the false posi- tive rate more than than the corresponding increase in the false negative rate, when creating RBFs. Finally, we demon- strate the advantages of an RBF over a Bloom filter in a dis- tributed network topology measurement application, where information about large stop sets must be shared among route tracing monitors.
Disciplines :
Computer science
Author, co-author :
Donnet, Benoît  ;  Université Catholique de Louvain - UCL > ICTEAM > INL
Baynat, Bruno
Friedman, Timur
Language :
English
Title :
Retouched Bloom Filters: Allowing Networked Applications to Flexibly Trade Off False Positives Against False Negatives
Publication date :
December 2006
Event name :
CoNEXT
Audience :
International
Main work title :
ACM CoNEXT
Peer reviewed :
Peer reviewed
Available on ORBi :
since 03 January 2012

Statistics


Number of views
52 (4 by ULiège)
Number of downloads
93 (1 by ULiège)

Bibliography


Similar publications



Contact ORBi