File PrefixFilter.h

↰ Parent directory (ADS/set)

The prefix filter of Even, Even and Morrison, beyond the book: an incremental filter, which takes insertions one at a time and no removals, of a set S of at most n keys, n known at its construction, answering maybe for every key of S and for a key out of S with a small probability.

Definition (ADS/set/PrefixFilter.h)

Detailed Description

Its first level is a table of m bins, each a pocket dictionary of 32 bytes (half a line of cache) that holds at most :math:` k = 25 ` fingerprints; its second level, the spare, is a blocked filter of Bloom [see File BlockedBloomFilter.h] that takes the fingerprints for which the bins have no room. A query reads one bin, and the spare only in the rare case described below, so that it costs one miss of the cache in almost every case, against two of the cuckoo filter [see File CuckooFilter.h]; an insertion never moves a fingerprint from a bin to another, so that its time does not grow with the load.

A key with the hash h has the fingerprint :math:` ( b , q , r ) : its bin :math: b = lfloor h_1 m / 2^{32} rfloor , :math: h_1 ` the high 32 bits of h, and its mini-fingerprint :math:` x = lfloor h_0 s / 2^{32} rfloor ` in :math:` [ 0 , s ) , :math: h_0 ` the low 32 bits of h and :math:` s = Q 2^R = 25 cdot 2^8 = 6400 , cut into the quotient :math: q = lfloor x / 2^8 rfloor < Q = 25 ` and the remainder :math:` r = x bmod 2^8 ` (both reductions by a product, as Lemire). A bin is the pocket dictionary PD(Q, R, k) = PD(25, 8, 25) of Bercea and Even: a header of :math:` Q + k = 50 ` bits that writes the number :math:` c_q ` of the remainders of each quotient q in unary, :math:` 1^{c_0} 0 , 1^{c_1} 0 cdots 1^{c_{24}} 0 ` from the low bit, 6 bits for the quotient of the largest fingerprint of the bin once it has overflowed (63 before), and a body of 25 bytes holding the remainders in the order of their quotients, those of one quotient (its run) in increasing order. The run of q is the slots :math:` [ z_{q-1} + 1 - q , z_q - q ) ` of the body, :math:` z_q ` being the place of the zero of rank q of the header ( :math:` z_{-1} = -1 ): with a zero put below the header, its zeros of ranks q and q + 1 are :math: z_{q-1} + 1 ` and :math:` z_q + 1 , both found by one pdep of :math: 3 cdot 2^q ` into the complement (BMI2), or by clearing the lowest bit q times on any machine; the pdep gives the two bits :math:` d_0 = 2^{z_{q-1}+1} ` and :math:` d_1 = 2^{z_q+1} , and the slots of the run are the bits of :math: ( d_1 / 2 - d_0 ) / 2^q , with no count of zeros. A query compares the 32 bytes of the bin with r at once (AVX-512 or AVX2, a byte at a time on any machine), stops if no byte of the body is equal, as it is for about 91 % of the keys out of S ( :math: 1 - ( 1 - 2^{-8} )^{23.75} ` of them have one), and otherwise tells whether one of the equal bytes is in the run of q. A key not found in the bin is compared with the bound of x in the bin, its largest fingerprint if it overflowed and above every x if not, which is the 6 bits of the quotient and the last byte of the body; the bound is out of the path of a key found, and the only branch on the bin besides those on the equal bytes is the rare one to the spare, out of line, a mispredicted branch on a load costing the loads of the queries in flight. An insertion finds the place of r in its run by counting the bytes of the run below r (one comparison of the 32 bytes), and moves the bytes above it by one within a register of 256 bits (AVX2), or within 4 words on any machine, while one more one goes into the header at the end of the run. The answers are the same on every machine.

The bins keep the prefix of their fingerprints. Each bin holds the smallest, in the order of :math:` x = 2^8 q + r , of the fingerprints that came to it, at most 25: an insertion into a full bin with :math: x ` not below the maximum :math:` x_{max} ` of the bin sends :math:` ( b , x ) ` to the spare, and one with :math:` x < x_{max} ` evicts :math:` x_{max} ` to the spare and takes its place; either way the bin is marked overflowed, by writing in the header the quotient of its maximum. Its maximum is the last byte of the body, with the quotient :math:` lfloor log_2 w rfloor - 24 ` of the last run, w the header (written again after an eviction), since the maximum of a bin never grows once it is full. Every fingerprint sent to the spare is then at least the maximum of its bin, and a query of x looks in the bin and, if x is not there, in the spare only if the bin has overflowed and :math:` x > x_{max} ` (a key of the bin is at most :math:` x_{max} ): a key of S is always found, the fingerprint equal to the maximum being in the bin. The spare holds the pairs :math: s b + x ` hashed again.

Analysis. Let n keys fall into :math:` m = lceil n / ( alpha k ) rceil ` bins, :math:` alpha = 0.95 , so that the load of a bin is the binomial :math: B sim mathrm{Bin}( n , 1 / m ) ` of mean :math:` alpha k . The fingerprints sent to the spare are :math: X = sum_b ( B_b - k )^+ `, of mean :math:`[ mathrm{E}[ X ] = n - m , mathrm{E}[ min( B , k ) ] ;, qquad

mathrm{E}[ X ] = n Bigl( 1 - frac{1}{m} Bigr) Pr[ B = k ] le frac{n}{sqrt{2 pi k}} quad text{for } m = n / k ` (Even et al., Theorem 5, by the bound of Stirling), i.e., 8.0 % of the keys at :math:` alpha = 1 , and 5.9 % at :math: alpha = 0.95 ` [see expectedSpareSize()]; X is concentrated around its mean, and the spare is built for :math:` n’ = 1.1 , mathrm{E}[ X ] ` fingerprints, as the paper suggests, at 12 bits each ( :math:` varepsilon’ approx 0.35 % ). A blocked filter of Bloom never fails: a spare that gets more than :math: n’ ` fingerprints only answers yes more often, so that every insertion succeeds until n keys are in, after which an insertion returns false and changes nothing.

A key out of S whose bin got j fingerprints is a false positive if its x is one of them, whether the bin kept it or sent it to the spare (which answers yes to it, holding it exactly), or if the bin overflowed, x is above the k-th smallest of the j fingerprints (with the probability :math:` ( j + 1 - k ) / ( j + 1 ) ` by the rank of x among them) and the spare answers yes to a pair it does not hold, with its probability :math:` varepsilon’ `: :math:`[ varepsilon approx sum_{j ge 0} Pr[ B = j ] Bigl( 1 -

Bigl( 1 - frac{1}{s} Bigr)^j + [ j > k ] , frac{j + 1 - k}{j + 1} , varepsilon’ Bigr) le frac{alpha k}{s} + frac{varepsilon’}{sqrt{2 pi k}} ;, ` the bound being Theorem 2 of the paper, :math:` k / s = 1 / 256 ` [see falsePositiveRate(), the sum at the current load]: 0.39 % when full, 0.37 % from the fingerprints and 0.02 % from the spare, about the 1 / 256 of a filter of fingerprints of 8 bits; a spare of 8 bits per fingerprint would save 0.26 bits per key and add 0.1 % of false positives. The bins take :math:` 256 / ( alpha k ) = 10.78 ` bits per key and the spare :math:` 12 cdot 1.1 , mathrm{E}[ X ] / n approx 0.77 `, about 11.55 in all for large n (a block of 256 bits for the spare at the least).

A key inserted j times takes j places of its bin, a duplicate past a full bin going to the spare. The adversarial keys whose hashes share their bin all go past the first 25 to the spare, which then answers yes to most of the queries of that bin, never no to a key of S.

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.

The contracts [see File Contract.h]: fewer than :math:` 2^{32} ` keys; a key inserted is maybe there, a postcondition; the count of a bin, an invariant. The operations are defined in PrefixFilter.tpp.

  1. Even, G. Even, A. Morrison, Prefix filter: practically and theoretically better than Bloom, Proceedings of the VLDB Endowment 15(7), 1311-1323, 2022, doi:10.14778/3523210.3523211

    1. Bercea, G. Even, A dynamic space-efficient filter with constant time operations, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020), LIPIcs 162, 11:1-11:17, 2020, doi:10.4230/LIPIcs.SWAT.2020.11 (the pocket dictionaries)

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

  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 (the spare)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes

Defines