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
A bloom filter is an extremely useful tool applicable to various fields of electronics and computers; it enables highly efficient search of extremely large data sets with no false negatives but a possibly small number of false positives. A counting bloom filter is a variant of a bloom filter that is typically used to permit deletions as well as additions of elements to a target data set. However, it is also sometimes useful to use a counting bloom filter as an approximate counting mechanism that can be used, for example, to determine when a specific web page has been referenced more than a specific number of times or when a memory address is a “hot” address. This paper derives, for the first time, highly accurate approximate false positive probabilities and optimal numbers of hash functions for counting bloom filters used in count thresholding applications. The analysis is confirmed by comparisons to existing theoretical results, which show an error, with respect to exact analysis, of less than 0.48% for typical parameter values.
- Analysis of Counting Bloom Filters Used for Count Thresholding
https://damrl.cs.fiu.edu/wp-content/uploads/sites/59/2021/12/RHIK_TR.pdf
- Hierarchical Bloom Filter Trees for Approximate Matching - https://commons.erau.edu/cgi/viewcontent.cgi?article=1489&context=jdfsl