File BloomFilter.h

↰ Parent directory (ADS/set)

The filter of Bloom, beyond the book: a set that may answer yes for an item it does not hold, but never no for one it holds, in m bits whatever the items.

Definition (ADS/set/BloomFilter.h)

Detailed Description

An item sets the k bits :math:` h_1 + i h_2 bmod m , i = 0 , … , k - 1, of two hashes, as Kirsch and Mitzenmacher showed to be as good as k independent hashes, and is maybe there if all its bits are set; after n insertions the probability of a false positive is about :math: ( 1 - e^{-k n / m} )^k , the least for :math: k = ( m / n ) ln 2 , i.e., about :math: 0.6185^{m/n} ` (1 % with about 9.6 bits per item). The two hashes come from the hash of the item mixed by splitmix64() [see File RandomHashing.h].

The contracts [see File Contract.h]: m >= 1 and k >= 1; an item inserted is always maybe there. The operations are defined in BloomFilter.tpp.

    1. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM 13(7), 422-426, 1970, doi:10.1145/362686.362692

  1. Kirsch, M. Mitzenmacher, Less hashing, same performance: building a better Bloom filter, Proceedings of ESA 2006, LNCS 4168, 456-467, 2006

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes