How Bloom, Counting, and Cuckoo Filters Optimize Database I/O

Bloom Filter

A Bloom filter uses a bitmap and multiple hash functions to test whether an element may be present; if all corresponding bits are set, the element is assumed to exist, otherwise it is definitely absent.

Problems of Bloom Filter

False positives: different elements may map to the same bits, causing a non‑existent element to be reported as present.

Deletion is not supported: removing an element would require clearing bits that may belong to other elements, leading to incorrect results.

Counting Bloom Filter

The counting variant replaces the bitmap with an array of counters; each hash position increments on insertion and decrements on deletion, mitigating the delete problem while still suffering from false positives.

Cuckoo Filter

To overcome Bloom filter limitations, the Cuckoo filter stores only a short fingerprint of each element in a bucketed array and supports deletions. It uses two possible bucket locations per element; if both are occupied, an existing fingerprint is evicted to its alternate location, repeating until a free slot is found or the table is deemed full.

Cuckoo Hash Structure

The simplest Cuckoo hash uses a one‑dimensional array with two hash functions mapping an element to two candidate positions.

p1 = hash1(x) % l
p2 = hash2(x) % l

If both positions are occupied, one fingerprint is kicked out and re‑hashed to its alternate location, potentially causing a cascade of evictions.

Issues and Optimizations

When the table becomes crowded, many evictions degrade insertion performance, and cycles can occur if elements repeatedly displace each other. Common optimizations include using more hash functions (e.g., three or four) and allowing multiple slots per bucket, which raises space utilization to 95‑99% while keeping query speed high.

Fingerprint‑Based Dual Position Calculation

Given a fingerprint fp and one bucket index p1, the alternate index is computed as p2 = p1 ^ hash(fp), enabling deletion without storing the original element.

fp = fingerprint(x)
p1 = hash(x) % l
p2 = p1 ^ hash(fp)  // XOR

This dual‑position property ensures that knowing any one index and the fingerprint uniquely determines the other, avoiding self‑eviction loops.