File CuckooFilter.h

↰ Parent directory (ADS/set)

The cuckoo filter of Fan, Andersen, Kaminsky and Mitzenmacher, beyond the book: a dynamic filter, which takes insertions and removals one at a time, of a set S of keys, answering maybe for every key of S and for a key out of S with a small probability.

Definition (ADS/set/CuckooFilter.h)

Detailed Description

It is a cuckoo table [see File CuckooHashing.h and File BucketCuckooTable.h] of :math:` 2^ell ` buckets of 4 places that keeps of each key only a fingerprint of f bits (8 or 16, the type F), never 0, so that 0 marks a free place.

A key k with the hash h has the fingerprint :math:` t = t( h ) , the high f bits of :math: h a bmod 2^{64} `, a an odd constant (1 if they are 0), which depend on every bit of h, so that t does not follow the bucket when h is a folded product of structured keys, such as consecutive integers, at the cost of one product of 64 bits, and the two buckets :math:`[ b_1 = h_1( h ) bmod 2^ell ;, qquad

b_2 = b_1 oplus g( t ) bmod 2^ell ;, ` :math:` h_1( h ) ` the high 32 bits of h and :math:` g( t ) ` the high half of a product of t by an odd constant (partial-key cuckoo hashing): the other bucket of a fingerprint is known from the fingerprint and either of its buckets, :math:` b_1 = b_2 oplus g( t ) , so that a fingerprint can be moved with no key at hand. An insertion puts t in a free place of :math: b_1 ` or of :math:` b_2 ; if both are full it evicts the fingerprint of a random place of one of them, moves it to its other bucket, and so on, at most 500 times; if the last fingerprint evicted finds no place it is kept aside, in a stash of one entry (the victim) that the queries read too, and the next insertion fails: a filter cannot be rehashed, since it keeps no key, so an insertion into a full filter returns false and changes nothing. A removal clears one place holding t in :math: b_1 ` or :math:` b_2 ` and moves the victim back into the table.

The 4 fingerprints of a bucket are one word (32 bits for f = 8, 64 for f = 16), and a query loads the two words before comparing: the places equal to t are the lanes of zero bits of :math:` u = w oplus t cdot ( 1 , dots , 1 ) , found for the 4 lanes at once by :math: lnot( ( ( u wedge m ) + m ) vee u vee m ) , m having all the bits but the top one of every lane (exact, with no carry from a lane to the next), which an insertion and a removal need to know the place; a query only asks whether one lane of the two words is zero, by :math: ( ( u_1 - mathbf{1} ) wedge lnot u_1 vee ( u_2 - mathbf{1} ) wedge lnot u_2 ) wedge lnot m ne 0 , :math: mathbf{1} ` having the bit 0 of every lane (Knuth, Warren): a borrow may mark a lane above a zero one, never a word with no zero lane, so that the test is exact. The victim is read only when there is one, a branch that is taken only when the filter is full.

Analysis. A query of a key out of S compares t with the at most :math:` 2 b = 8 ` fingerprints of its buckets, each equal to t with probability :math:` 1 / ( 2^f - 1 ) , so that at the load :math: alpha ` (the fraction of places taken) the false positives are :math:`[ varepsilon = 1 - Bigl( 1 - frac{1}{2^f - 1} Bigr)^{8 alpha}

le frac{8 alpha}{2^f - 1} ;, ` at most 3.1 % for f = 8 and 0.012 % for f = 16, in :math:` f / alpha ` bits per key. With 2 choices and buckets of d places every key finds a place with high probability up to the load :math:` 1 / ( 1 + varepsilon ) ` for any :math:` varepsilon > ( 2 / e )^{d-1} ` (Dietzfelbinger and Weidling), 0.71 for d = 4, a bound that is far from tight: the insertions by 500 evictions reach about 0.95 in practice (Fan et al.), from 0.97 at :math:` 2^{10} ` buckets to 0.95 at :math:` 2^{22} ` in the tests of Namespace ADS. The buckets of a fingerprint are not independent, :math:` b_2 ` taking only :math:` 2^f - 1 ` values relative to :math:` b_1 `, which at f = 8 costs at most 1 % of that load. The constructor for n keys takes the fewest buckets, a power of 2, that hold n keys at the load 0.94. A key inserted j times takes j places, and is removed once by each removal; past its 8 places, it fills the filter.

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. A key removed must have been inserted, which no contract can check: the removal of another key may clear the fingerprint of a key of S, a false negative. The operations are defined in CuckooFilter.tpp.

  1. Fan, D. G. Andersen, M. Kaminsky, M. D. Mitzenmacher, Cuckoo filter: practically better than Bloom, Proceedings of the 10th ACM International Conference on emerging Networking Experiments and Technologies (CoNEXT 2014), 75-88, 2014, doi:10.1145/2674005.2674994

  1. Pagh, F. F. Rodler, Cuckoo hashing, Journal of Algorithms 51(2), 122-144, 2004, doi:10.1016/j.jalgor.2003.12.002

  1. Dietzfelbinger, C. Weidling, Balanced allocation and dictionaries with tightly packed constant size bins, Theoretical Computer Science 380(1-2), 47-68, 2007, doi:10.1016/j.tcs.2007.02.054

  1. Kirsch, M. Mitzenmacher, U. Wieder, More robust hashing: cuckoo hashing with a stash, SIAM Journal on Computing 39(4), 1543-1561, 2009, doi:10.1137/080728743 (the stash)

    1. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Part 1, Addison-Wesley, 2011, section 7.1.3 (the broadword computing, the test of a zero byte)

    1. Warren, Hacker’s Delight, 2nd ed., Addison-Wesley, 2013, section 6-1 (the first zero byte), ISBN 978-0-321-84268-8

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes

Defines