Retouched Bloom Filters: Allowing Networked Applications to Flexibly Trade Off False Positives Against False Negatives

Computer Science – Networking and Internet Architecture

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

This is a new version of the technical reports with improved algorithms and theorical analysis of algorithms

Scientific paper

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, 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 generating 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 and improved algorithms that decrease the false positive rate more than than the corresponding increase in the false negative rate, when creating RBFs. Finally, we demonstrate the advantages of an RBF over a Bloom filter in a distributed network topology measurement application, where information about large stop sets must be shared among route tracing monitors.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Retouched Bloom Filters: Allowing Networked Applications to Flexibly Trade Off False Positives Against False Negatives does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Retouched Bloom Filters: Allowing Networked Applications to Flexibly Trade Off False Positives Against False Negatives, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Retouched Bloom Filters: Allowing Networked Applications to Flexibly Trade Off False Positives Against False Negatives will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-79888

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.