Smaller and More Flexible Cuckoo Filters

Cuckoo filters are space-efficient approximate set membership data structures with a controllable false positive rate (FPR) and no false negatives, similar to Bloom filters. In contrast to Bloom filters, Cuckoo filters store multi-bit fingerprints of keys in a hash table using variants of Cuckoo hashing, allowing each fingerprint to be stored at a small number of possible locations. Existing Cuckoo filters use fingerprints of \((k+3)\) bits per key and an additional space overhead factor of at least 1.05 to achieve an FPR of \(2^{-k}\). For \(k = 10\), this amounts to 1.365 \(kn\) bits to store \(n\) keys, which is better than 1.443 \(kn\) bits for Bloom filters. The +3 for the fingerprint size is required to balance out the multiplied FPR caused by searching for the fingerprint at \(2^3 = 8\) locations. In the original Cuckoo filter, the number of hash table buckets is restricted to a power of two, which may lead to much larger space overheads, up to \(2.1\, (1+3/k)\, kn\) bits (e.g. 2.73 \(kn\) bits for \(k = 10\)).