File RibbonFilter.h

↰ Parent directory (ADS/set)

The standard Ribbon filter of Dillinger and Walzer, 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^{-r} , for results of r bits (8 or 16, the type F), in :math: r ( 1 + varepsilon ) ` bits per key, :math:` varepsilon ` a small overhead [see below], against the :math:` 1.44 r ` of a filter of Bloom with the same false positives [see File BloomFilter.h] and the :math:` 1.125 r ` of the binary fuse filter at large n [see File BinaryFuseFilter.h].

Definition (ADS/set/RibbonFilter.h)

Detailed Description

The filter is the solution Z, a matrix of m rows of r bits over :math:` mathbb{F}_2 , of the linear system of the n keys: a key k with the hash h has the start :math: s( h ) in { 0 , dots , m - 64 } , the coefficients :math: c( h ) , a word of w = 64 bits whose bit 0 is 1, and the fingerprint :math: f( h ) ` of r bits, and its equation is \([ \bigoplus_{j = 0}^{63} c_j( h ) \, Z_{s( h ) + j} = f( h ) \;, \` the XOR of the rows of Z selected by the bits of c from the row :math:\) s( h ) . A key is maybe in S if its equation holds; a key out of S meets it with probability :math: 2^{-r} , the left side being a random word independent of :math: f( h ) , so that the false positives are :math: varepsilon_{fp} = 2^{-r} , about 0.39 % for r = 8 and 0.0015 % for r = 16. The start is :math: s = lfloor h ( m - 63 ) / 2^{64} rfloor ` (Lemire), with no remainder.

The coefficients are :math:` c( h ) = ( h a bmod 2^{64} ) vee 1 , a an odd constant, the start depending on the high bits of h and the fingerprint :math: f( h ) ` on its bits 0 to r - 1 and 32 to 31 + r.

The build solves the system by Gauss elimination on the fly (Rapid Incremental Boolean Banding ON the fly, Dillinger and Walzer): the equations are kept in echelon form, row i holding either no equation or one whose first coefficient is in column i; a new equation :math:` ( s , c , f ) ` goes to row s if it is free, and otherwise is XORed with the equation of row s and shifted to the first column of the result that is 1, until it finds a free row; an equation that becomes 0 is redundant if its right side is 0 too (a repeated key), and makes the system unsolvable otherwise. The rows are then solved from the last, :math:` Z_i = f_i oplus bigoplus_{j ge 1} c_{i,j} Z_{i+j} `, by keeping for each of the r columns the word of the 64 rows below, so that a row costs r parities of a word; a row with no equation takes a pseudorandom value. The banding prefetches the rows of the key 16 places ahead (Chen et al.), whose start is known from its hash, so that the misses of the cache of several keys overlap. With AVX-512 the back substitution takes 4 rows at a time, 8 columns per register: with W the words of the rows from i, the row i - d, d = 1, …, 4, is :math:`[ Z_{i-d} = f_{i-d} oplus mathrm{parity}bigl( ( c_{i-d} gg d )

wedge W bigr) oplus bigoplus_{k=1}^{d-1} c_{i-d,k} , Z_{i-d+k} ;, ` the 4 parities taken from the same W at once and the bits of the new rows among them added after, by masks, so that the chain of dependences is one parity per 4 rows instead of one per row; the solution is the same as row by row. The solution is stored interleaved: for each block of 64 rows, r words, the j-th of which holds the column j of the block, so that a query reads the 2 r words of the blocks of its 64 rows, which are consecutive, and makes each bit of its result by the parity of :math:` ( c ll o ) wedge u oplus ( c gg ( 64 - o ) ) wedge v , o the offset of s in its block and u, v the words of the column in the two blocks. The blocks are aligned to the lines of cache of 64 bytes, each line holding 8 columns of a block, and a query takes the 8 parities of a line at once: with AVX-512 the 8 words of each block in one register, the parity of each byte by a table of the 16 nibbles (vpshufb) after folding its two halves, and the 8 bytes of a word summed by vpsadbw, whose bit 0 is the parity (the population count of Mula, Kurz and Lemire reduced modulo 2); with AVX2 the same on 4 words at a time; on any machine by one popcount per word. A query compares the 8 bits of a line with those of :math: f( h ) ` before reading the next line, so that a key out of S reads one line of each block with probability :math:` 1 - 2^{-8} `: 2 lines for r = 8 and r = 16 alike, against the 4 lines of a key of S for r = 16. The answers are the same on every machine.

Space and success. For m rows the filter takes :math:` r m ` bits (and r words of padding). Dietzfelbinger and Walzer show that a system of :math:` n = ( 1 - varepsilon ) m ` equations with random blocks of length :math:` L = O( log n / varepsilon ) ` has full rank with high probability, its elimination taking :math:` O( m / varepsilon^2 ) ` expected time; with L = w = 64 fixed, the overhead needed grows as :math:` log n `, and the build takes :math:`[ m = n ( 1 + varepsilon ) ;, qquad varepsilon =

maxbigl( 0.01 ,,, 0.0083 log_2 n - 0.025 bigr) ;, ` rounded up to a multiple of 64 and at least 64: about 9 % at :math:` 10^5 ` keys and 14 % at :math:` 10^6 `, i.e., 8.9 and 9.1 bits per key for r = 8. If the system has no solution the build draws a new seed, and after every 4 failures adds 2 % of n rows.

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 keys may repeat: a repeated key gives a redundant equation, and counts in size() once per occurrence.

The contracts [see File Contract.h]: fewer than :math:` 2^{32} ` 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 RibbonFilter.tpp.

    1. Dillinger, S. Walzer, Ribbon filter: practically smaller than Bloom and Xor, arXiv:2103.02515, 2021, https://arxiv.org/abs/2103.02515

  1. Lemire, Fast random integer generation in an interval, ACM Transactions on Modeling and Computer Simulation 29(1), 3:1-3:12, 2019, doi:10.1145/3230636 (the start by a product)

  1. Dietzfelbinger, S. Walzer, Efficient Gauss elimination for near-quadratic matrices with one short random block per row, with applications, Proceedings of ESA 2019, LIPIcs 144, 39:1-39:18, 2019, doi:10.4230/LIPIcs.ESA.2019.39

  1. Chen, A. Ailamaki, P. B. Gibbons, T. C. Mowry, Improving hash join performance through prefetching, Proceedings of ICDE 2004, 116-127, 2004, doi:10.1109/ICDE.2004.1319989 (the prefetch of the rows of the keys ahead, in the banding)

  1. Mula, N. Kurz, D. Lemire, Faster population counts using AVX2 instructions, The Computer Journal 61(1), 111-120, 2018, doi:10.1093/comjnl/bxx046 (the counts of the bytes by vpshufb and vpsadbw, here their parities)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes

Defines