Part 10: Cuckoo Filters - Sizing and Creating

In previous articles in this series we saw several versions of Bloom Filters and then Counting Filters and Quotient Filters, which allow deletions. Here we'll see a new structure, Cuckoo Filters, with better performance and lower storage requirements.

---

Cuckoo Filters

In previous sections, we started with Bloom Filters, which don't allow deletions; we then touched on Counting Bloom Filters to address that, and eventually moved to Quotient Filters without that restriction. We'll now look at Cuckoo Filters, introduced in 2014 by Bin Fan, David Andersen, Michael Kaminsky, and Michael Mitzenmacher in their "Cuckoo Filter: Practically Better Than Bloom" paper. 

This new filter beats Quotient Filters in performance and space. It uses a structure of buckets, each with a fixed number of available slots, where fingerprints are stored. Each value to be stored is represented by a fingerprint and is associated with two bucket indices; the value may be stored in a free slot of either bucket. If both buckets are full, the filter kicks out an existing value (which must then move to its alternate bucket) and stores the new value in its place. This behavior reminds us of some cuckoo birds, which are brood parasites: a female lays her egg in another bird's nest, and when the cuckoo chick hatches, it instinctively pushes the host's eggs or chicks out. The newcomer takes the slot by evicting whatever was there. 

How Cuckoo Filters Work

A CF has b buckets; to allow using efficient binary operators, b is a power of 2. Each bucket has s slots, and as in a QF, we won't store values in the slots; just fingerprints. We won't accept zero as a fingerprint; that will represent an empty slot. Fingerprints in a bucket will not be in any particular order. For each value to be included in a CF, we will compute three results:

• fp, a fingerprint, p bits long; p is chosen to achieve a low false-positive rate.
• i1, a first index, calculated as hash(value) - we assume this returns a valid bucket number.
• i2, a second index, calculated as i1 XOR hash(fp), which must also be a valid bucket number.

Why are indices calculated this way? The key is that given the fp fingerprint and one index, you can find the other one by doing an XOR with hash(fp):

• Given i1, the calculation produces i1 XOR hash(fp), which is i2 by definition.
• Given i2, we calculate i1 XOR hash(fp) XOR hash(fp) and since for all values Y XOR Y=0 and X XOR 0 = X the result is just i1.

How does this work? If we are searching for a value, we need to calculate its fingerprint and indices, then check both buckets to see whether the fingerprint is in either. If we don't find it, the answer is a definite "no; not present"; if we do, the answer is a "may be present", as with other filters.

Removing a value is equally easy; if you search for the value and find it, you just remove it from the corresponding bucket. The same considerations we saw for previous filters, such as the possibility of removing the wrong value, remain unchanged.

Finally, how do additions work? This is where things get interesting. We calculate the fingerprint and both indices. If either bucket has space, we add the fingerprint there, and we're done. If not, we randomly pick a slot and put the new fingerprint there. We will calculate the other index for the removed value and attempt to place it in the other bucket. If there's space, we store it; if not, we repeat the "push" by picking a random value from that slot, and so on. This kicking process could enter a loop; we will consider that later, when we see actual code.

Creating a Cuckoo Filter

We expect to store n items in b buckets (b must be a power of 2) with s slots each, and we want a maximum load factor of α. The original paper suggests s=4 for probabilistic reasons (it could go up to 8) so we'll go with that. The buckets provide bs slots in total, so α = n/bs. Accordingly, we want b to be a power of 2 at least as large as n/(sα).

Then, we need to determine the fingerprint length in bits, p. A lookup checks two candidate buckets, each with at most s fingerprints. If fingerprints are uniformly distributed, the false-positive probability is approximately ε ≈ 2_s_/2^p, so p should be ⌈log₂(2_s_/ε)⌉.

We can now show the CF creation code.

const EPSILON = 0.01;
➊ const ALPHA = 0.9;

const createCuckooFilter = (n, eps = EPSILON) => {
➋const s = 4;

➌const b = nextPowerOfTwo(n / (s * ALPHA));

➍const p = Math.ceil(Math.log2((2 * s) / eps));
  if (p > 24) {
    throw new Error(
      "Cuckoo filter: epsilon exceeds 24-bit fingerprint limit"
    );
  }

➎return {
    n,
    b,
    s,
    p,
    c: 0,
    buckets: Array.from({ length: b }, () => [])
  };
};

The recommendations for α are between 0.90 and 0.95; here ➊ we chose the former. Similarly, for slots ➋ the usual value for s is 4; higher values are possible but not recommended. We use the formulae we derived for b ➌ and p ➍; we added an extra check so we don't require too large fingerprints. (As an aside, we could also add a check to make sure that b s-sized arrays do not require too much space.) We finally ➎ return an object also including c, the running count of elements in the CF, and buckets, the buckets themselves. (Check question 11½–5 in a previous article to avoid a big mistake.) Buckets just have empty arrays to begin with, but when adding new values we'll make sure they do not go past s slots.

---

Bye for now! In the next article in the series, we will see how to search and update a Cuckoo Filter.