An Improved Construction for Counting Bloom Filters

Flavio Bonomi, Michael Mitzenmacher, Rina Panigrahy, Sushil Singh, George Varghese

Abstract

A counting Bloom filter (CBF) generalizes a Bloom filter data structure so as to allow membership queries on a set that can be changing dynamically via insertions and deletions. As with a Bloom filter, a CBF obtains space savings by allowing false positives. We provide a simple hashing-based alternative based on d-left hashing called a d-left CBF (dlCBF). The dlCBF offers the same functionality as a CBF, but uses less space, generally saving a factor of two or more. We describe the construction of dlCBFs, provide an analysis, and demonstrate their effectiveness experimentally.
BibTeX
@inproceedings{bonomi2006improved,
  author = {Flavio Bonomi and Michael Mitzenmacher and Rina Panigrahy and Sushil Singh and George Varghese},
  title = {{An Improved Construction for Counting Bloom Filters}},
  booktitle = {ESA},
  year = {2006},
  doi = {10.1007/11841036\_61},
}

Loading related content...

Figure