Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not – in other words, a query returns either "possibly in set" or "definitely not in set".
A counting Bloom filter (CBF) generalizes a Bloom filter data structure so as to allow membership queries on a set that can bechanging dynamically via insertions and deletions. As with a Bloom filter,a CBF obtains space savings by allowing false positives. We provide asimple hashing-based alternative based ond-left hashing called ad-leftCBF (dlCBF). The dlCBF offers the same functionality as a CBF, butuses less space, generally saving a factor of two or more. We describethe construction of dlCBFs, provide an analysis, and demonstrate theireffectiveness experimentally