Problems of Bloom Filter

Bloom filters cannot remove existing items without rebuilding the entire filter
Efforts to extend Bloom filters to support deletions introduce significant space and performance overhead

Contributions of Cuckoo Filter

Cuckoo filters support adding and removing items dynamically
Cuckoo filters provide higher lookup performance
Cuckoo filters use less space than Bloom filters under many scenarios.

Cuckoo Hashing Basics

Components:

Two hash tables T1 and T2, each with m elements
Two hash functions: h1 and h2, $\mathcal{U}\rightarrow [m]$

Note: Every element $x\in\mathcal{U}$ will either be at position $h1(x)$ in $T1$ or $h2(x)$ in $T2$

Operations:

Lookup: check $T1[h1(x)]$ and $T2[h2(x)]$ , test if they are equal to x.
Insert
- First, check $T1[h1(x)]$ and $T2[h2(x)]$
- If one of these 2 buckets is available, insert the entry into that slot.
- If no buckets are available
  - choose one hash table (e.g. $T1$ ) and kick out the element (element $e = T1[h1(x)]$ ).
  - Insert element e to $T2$ $T 2$ (because it is just replaced from $T1$ $T 1$ )
    - If there is still a collision, repeat the steps above until a maximum number of displacements is reached.

Performance:

space: The table place can be 95% filled with proper configuration
time
- insertion: amortized $O(1)$

Cuckoo Hashing Variants

As shown in the following figure

2 hash functions and 1 hash table
2 hash functions and 1 4-way hash table

How does Cuckoo Filter Do?

To make cuckoo filters highly space-efficient, use a multi-way associative cuckoo hash table.
To reduce hash table size, each item is first hashed into a constant-sized fingerprint before being inserted into the hash table.

Insertion

Cuckoo filters use original data to calculate hash value but only store the fingerprint of an element, which makes it hard to relocate. Relocations require the original data value.

To overcome this problem, cuckoo filters utilize a technique called partial-key cuckoo hashing to derive an item’s alternate location based on its fingerprint.

For each item x, the cuckoo filter calculates the indexed of the two candidate buckets:

$h_1(x)=\text{hash}(x),\\ h_2(x)=h_1(x)\oplus \text{hash}(x\text{'s fingerprint})$