File BloomVariants.h

↰ Parent directory (ADS/set)

The variants and the analysis of the filter of Bloom [see File BloomFilter.h for the standard one], beyond the book:

Definition (ADS/set/BloomVariants.h)

Detailed Description

  • SpectralBloomFilter, the filter of Cohen and Matias for multisets: m counters instead of bits, an insertion of x with multiplicity f adds f to its r counters and a removal subtracts it, and the multiplicity of x is estimated by the least of its r counters (the minimum selection), never below the true one and above it only when all r counters of x are shared, with the probability of a false positive of the filter of Bloom with the same m, n and r. With counters of a few bits it is the counting filter of Fan, Cao, Almeida and Broder, which removes keys; a counter that reaches its largest value sticks there, as they do, so that a removal never makes a false negative;

  • PartitionedBloomFilter, whose m bits are cut into r parts of m / r bits, each hash setting one bit of its own part, so that the r bits of a key are distinct: the expected bits set and the false positives are about those of the standard filter, :math:` ( 1 - e^{-r n / m} )^r `, with a slightly smaller variance (Grandi);

  • the analysis: bloomFalsePositive(), the probability :math:` ( 1 - ( 1 - 1 / m )^{r n} )^r approx ( 1 - e^{-r n / m} )^r , least for :math: r = ( m / n ) ln 2 , where a bit is 0 with probability 1 / 2 and the error is :math: 0.6185^{m/n} ` [see bloomBestHashes()]; bloomLowerBound(), the :math:` n log_2( 1 / epsilon ) ` bits that any structure with false positives :math:` epsilon ` and no false negative needs, of which a filter of Bloom uses :math:` log_2 e approx 1.44 ` times [see bloomBits()]; compressedBloom(), the trade-off of Mitzenmacher between the size of a filter and its entropy, by which a larger and sparser filter, compressed by an arithmetic coder, sends fewer bits for the same false positives;

  • bloomIntersection(), the intersection of two sets on two machines by sending the filter of A and receiving the keys Q of B that it accepts, :math:` A cap B subseteq Q , then :math: A cap Q : about :math: | A cap B | + 0.6185^{m_A / | A |} | B | ` keys travel back, instead of the whole A.

The r hashes of a key are :math:` h_1 + i h_2 bmod m ` of two hashes, as in BloomFilter. Other filters of today, closer to the lower bound for small false positives, are the quotient filters (Bender et al.), the cuckoo filters (Fan et al.) and the xor filters (Graf and Lemire), the latter with about :math:` 1.23 log_2( 1 / epsilon ) ` bits per key.

The contracts [see File Contract.h]: m >= 1 and r >= 1 (m >= r for the partitioned filter); a removal of x with multiplicity f only if the estimate of x is at least f; an item inserted is always maybe there and its estimate is at least its multiplicity, postconditions; for the analysis m >= 1, n >= 0, r >= 1, 0 < epsilon < 1. The functions are defined in BloomVariants.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 8 (section 8.7)

  1. Cohen, Y. Matias, Spectral Bloom filters, Proceedings of SIGMOD 2003, 241-252, 2003, doi:10.1145/872757.872787

  1. Fan, P. Cao, J. Almeida, A. Z. Broder, Summary cache: a scalable wide-area web cache sharing protocol, IEEE/ACM Transactions on Networking 8(3), 281-293, 2000, doi:10.1109/90.851975

  2. Mitzenmacher, Compressed Bloom filters, IEEE/ACM Transactions on Networking 10(5), 604-612, 2002, doi:10.1109/TNET.2002.803864

    1. Broder, M. Mitzenmacher, Network applications of Bloom filters: a survey, Internet Mathematics 1(4), 485-509, 2004, doi:10.1080/15427951.2004.10129096

  1. Grandi, On the analysis of Bloom filters, Information Processing Letters 129, 35-39, 2018, doi:10.1016/j.ipl.2017.09.004

    1. Graf, D. Lemire, Xor filters: faster and smaller than Bloom and cuckoo filters, ACM Journal of Experimental Algorithmics 25, article 1.5, 2020, doi:10.1145/3376122

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes

Functions