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

Free registration required

Executive Summary

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.

  • Format: PDF
  • Size: 694.82 KB