File BlockedBloomFilter.h

↰ Parent directory (ADS/set)

The blocked filter of Bloom, beyond the book: the engineered filter of Namespace ADS [see File BloomFilter.h for the standard one and File BloomVariants.h for its variants].

Definition (ADS/set/BlockedBloomFilter.h)

Detailed Description

Its bits are cut into blocks of 256 bits, 8 words of 32 bits, and an item sets 8 bits of one block, one in each word: the block is :math:` lfloor h_1 B / 2^{32} rfloor ` for B blocks, the bit of the word i is the top 5 bits of :math:` h_0 s_i bmod 2^{32} ` for 8 odd constants :math:` s_i , :math: h_1 ` and :math:` h_0 ` being the high and the low half of the hash of the item. A query then reads one block, i.e., one line of cache, instead of the k lines of the standard filter, and makes its 8 bits by one product, one shift and one variable shift of a vector of 8 words (AVX2), or by 8 products of 32 bits on any machine, with the same result.

Putting the bits of an item in one block costs false positives: the blocks get different numbers of items (a Poisson number of mean :math:` lambda = 256 n / m ), and the crowded ones answer yes more often, so that the false positives are the mean over the loads j of the probability :math: ( 1 - ( 1 - 1 / 32 )^j )^8 ` of a block of j items [see falsePositiveRate()]: about 1.26 % at 10 bits per item, against 0.82 % of the standard filter with 7 hashes, and 0.31 % at 13.5 bits against 0.15 % (Putze, Sanders and Singler). The split of the 8 bits into 8 words is that of the filters of Impala and of the format Parquet; the number of blocks is any, not a power of 2, so that the bits per item are those asked.

The hash of an item is h( x ), taken as it is if H declares is_avalanching [see File FastHash.h], and mixed by hashWord() otherwise (the identity of std::hash on the integers); insertHash() and maybeHash() take a hash of 64 bits that is already random.

The contracts [see File Contract.h]: at least one block; an item inserted is maybe there, a postcondition; two filters united have the same number of blocks. The operations are defined in BlockedBloomFilter.tpp.

  1. Putze, P. Sanders, J. Singler, Cache-, hash-, and space-efficient Bloom filters, Journal of Experimental Algorithmics 14, 4.4, 2009, doi:10.1145/1498698.1594230

Apache Parquet, Split block Bloom filter, 2019, https://github.com/apache/parquet-format/blob/master/BloomFilter.md

  1. Lemire, Fast random integer generation in an interval, ACM Transactions on Modeling and Computer Simulation 29(1), 3, 2019 (the block by a product instead of a remainder)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes