File BinaryFuseFilter.h

↰ Parent directory (ADS/set)

The binary fuse filter of Graf and Lemire, beyond the book: a static filter of a set S of n keys, built once, which answers maybe for every key of S and for a key out of S with probability about :math:` 2^{-b} , in about :math: 1.13 b ` bits per key for fingerprints of b bits (8 or 16), against the :math:` 1.44 b ` of a filter of Bloom with the same false positives [see File BloomFilter.h and File BlockedBloomFilter.h] and the :math:` 1.23 b ` of the xor filter, of which it is the successor.

Definition (ADS/set/BinaryFuseFilter.h)

Detailed Description

A key k with the hash h has 3 places :math:` h_0 , h_1 , h_2 ` of an array F of fingerprints, and is maybe in S if :math:` F[ h_0 ] oplus F[ h_1 ] oplus F[ h_2 ] = f( h ) , its fingerprint. The array is cut into segments of L places (a power of 2): :math: h_0 ` is a place of the first C L ones, by a product of h, and :math:` h_1 ` and :math:` h_2 ` are in the two segments that follow, at places given by other bits of h, so that the 3 places of a key are within 3 consecutive segments (the spatial coupling that lets the array have only about 1.125 n places for large n, against 1.23 n for 3 places anywhere).

The build solves the system of the n equations by peeling: a place reached by exactly one key is solved last for that key, which is then removed from its other two places, and so on; each place keeps the number of its keys, the XOR of their hashes and the XOR of the indices (0, 1 or 2) by which they reach it, so that a place left with one key tells the hash of that key and which of its places it is, and the peeling touches nothing but these arrays. If every key is peeled, the fingerprints are assigned in the reverse order of the peeling, :math:` F[ h_i ] = f( h ) oplus F[ h_{i+1} ] oplus F[ h_{i+2} ] , the place :math: h_i ` being still free when its key is reached; otherwise (with probability well below 1 % for the sizes of the paper) the build draws a new seed. Before the counts, the hashes are sorted by their segment by a counting sort, so that the counts and the peeling walk the arrays in order and stay in the cache. The keys may repeat: a key that occurs twice has twice the same hash, which cannot be peeled, so a build that fails removes the equal hashes before drawing a new seed.

The hash of a key is h( k ), taken as it is if H declares is_avalanching [see File FastHash.h] and mixed by hashWord() otherwise; for each seed it is mixed once more by a folded product with the seed. The array has at most :math:` 2^{32} ` places.

The contracts [see File Contract.h]: fewer than :math:` 2^{31} ` keys; after the build every key is maybe there, an audit. A build that draws 1000 seeds with no success throws std::runtime_error. The operations are defined in BinaryFuseFilter.tpp.

    1. Graf, D. Lemire, Binary fuse filters: fast and smaller than xor filters, ACM Journal of Experimental Algorithmics 27, 1.5, 2022, doi:10.1145/3510449

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

  1. Dietzfelbinger, S. Walzer, Dense peelable random uniform hypergraphs, Proceedings of ESA 2019, LIPIcs 144, 38, 2019 (the spatial coupling)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes