Smaller and More Flexible Cuckoo Filters

Johanna Elena Schmitz, Jens Zentgraf 1, Sven Rahmann · 2025

Read Smaller and More Flexible Cuckoo Filters by Johanna Elena Schmitz, Jens Zentgraf 1, Sven Rahmann (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-05847.txt.

Introduction

Filters that answer set membership questions fast and small sit inside databases and networks everywhere. Johanna Elena Schmitz, Jens Zentgraf, and Sven Rahmann shrink one such filter in a 2025 paper. Cuckoo filters store short key prints in a hash table and can err on the yes side only.

Two changes drive the gain. The table no longer needs a size that is a power of two. Slots also overlap in sliding windows, so each print has fewer hiding spots to check. The new layout beat rival filters on size in real tests, with like query speed. Inserts ran slower, a fair trade for the saved space.

Catalog record

CREATORJohanna Elena Schmitz, Jens Zentgraf 1, Sven Rahmann
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-05847

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Smaller and More Flexible Cuckoo Filters Johanna Elena Schmitz, Jens Zentgraf 1, Sven Rahmann Abstract Cuckoo filters are space-efficient approximate set membership data structures with a controllable false positive rate (FPR) and zero 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 ) (k+3) bits per key and an additional space overhead factor of at least 1.05 1.05 to achieve an FPR of 2 − k 2^{-k} . For k = 10 k=10 , this amounts to 1.365 ​ k ​ n 1.365\,kn bits to store n n keys, which is better than 1.443 ​ k ​ n 1.443\,kn bits for Bloom filters. The + 3 +3 for the fingerprint size is required to balance out the multiplied FPR caused by looking for the fingerprint at several locations. In the original Cuckoo filter, the number of hash table buckets is restricted to a power of 2, which may lead to much larger space overheads, up to 2.1 ​ ( 1 + 3 / k ) ​ k ​ n 2.1\,(1+3/k)\,kn bits. We present two improvements of Cuckoo filters. First, we remove the restriction that the number of buckets must be a power of 2 by using a different placement strategy. Second, we reduce the space overhead factor of Cuckoo filters to 1.06 ​ ( 1 + 2 / k ) 1.06\,(1+2/k) by using overlapping windows instead of disjoint buckets to maintain the load threshold of the hash table, while reducing the number of alternative slots where any fingerprint may be found. A detailed evaluation demonstrates that the alternative memory layout based on overlapping windows decreases the size of Cuckoo filters not only in theory, but also in practice. A comparison with other state-of-the art filter types, Prefix filters and Vector Quotient filters (VQFs), shows that the reduced space overhead makes windowed Cuckoo filters the smallest filters supporting online insertions, with similarly fast queries, but longer insertion times. The improved Cuckoo filters are also more flexible in the sense that Prefix filters and VQFs only support a restricted set of FPRs. Our implementation of bucketed and windowed Cuckoo filters, and the workflows to reproduce all results are available at https://gitlab.com/rahmannlab/cuckoo-filters . Algorithmic Bioinformatics, Faculty of Mathematics and Computer Science, Saarland University and Saarbrücken Graduate School of Computer Science and Center for Bioinformatics Saar, Saarland Informatics Campus, Saarbrücken, Germany [email protected]://orcid.org/0009-0002-6377-2561 Algorithmic Bioinformatics, Faculty of Mathematics and Computer Science, Saarland University and Saarbrücken Graduate School of Computer Science and Center for Bioinformatics Saar, Saarland Informatics Campus, Saarbrücken, Germany [email protected]://orcid.org/0000-0001-9444-2755 Algorithmic Bioinformatics, Faculty of Mathematics and Computer Science, Saarland University and Center for Bioinformatics Saar, Saarland Informatics Campus, Saarbrücken, Germany [email protected] 0000-0002-8536-6065 ccs Theory of computation Bloom filters and hashing keywords Cuckoo hashing, approximate set membership, probabilistic filter, power of choices † † runningauthor: J. E. Schmitz, J. Zentgraf and S. Rahmann † † copyright: Johanna Elena Schmitz, Jens Zentgraf and Sven Rahmann † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction Probabilistic filters. Probabilistic filters are space efficient data structures for fast set membership queries. They have many practical applications, such as for database systems [ 24 ] , networks [ 14 , 25 ] , storage systems [ 21 ] and sequence analysis in computational biology [ 17 , 20 , 23 ] . A probabilistic filter represents a set K of keys from a key universe \mathcal{U} and supports at least two operations: (1) inserting a key, and (2) querying if a key is contained in the filter. Instead of storing an exact representation of the set K , the keys are fuzzily represented in a way that queries for keys that were inserted into the filter are always correctly answered (no false negative results). Queries about keys that were not inserted, are correctly answered most of the time, but sometimes incorrectly positively. The probability of obtaining a false positive answer is called the false positive rate (FPR). The FPR is controlled by the user and related to the space requirements of the filter. To represent an arbitrary set of keys K with cardinality |K|=n with an FPR of \varepsilon=2^{-k} , the theoretically optimal space requirement is nk bits. Practical implementations of filters need Cnk bits with an overhead factor C>1 that differs between filter types. Different filter types try to achieve small C and fast insertion and query times; often with different trade-offs between space and time efficiency. In addition, some filter variations support additional operations, such as deletion of keys (dynamic filters), counting the number of times a key was inserted (counting filters), or even storing arbitrary values with the keys (probabilistic key-value stores). Other variants optimize the space requirements for a fixed set of keys, where the complete set of keys has to be known before filter construction starts (static filters). Filter variants. Bloom filters [ 2 ] were first introduced in 1970 and are still among the most commonly used filters. Bloom filters, when optimally configured for an FPR of 2^{-k} , store a bit array with m:=(1/\ln 2)\,nk\approx 1.443\,nk bits. Disadvantages of Bloom filters are the relatively high overhead of 44.3% and slow insertion and query times. Blocked Bloom filters [ 29 ] achieve faster insertion and query times at the cost of even larger space, and the recent BlowChoc filters [ 30 ] keep the advantages of Blocked Bloom filters while reducing the space requirements, sometimes even below those of standard Bloom filters. However, alternative filter designs often perform better than Bloom filters. Cuckoo filters [ 11 ] , (Vector) Quotient filters [ 13 , 28 ] and Prefix filters [ 10 ] store a k -bit fingerprint in a hash table instead of distributed bits in a bit array. This design allows for storing additional values together with the key fingerprints, simply by using additional bits, giving us not only a probabilistic set membership data structure, but also a probabilistic key-value store without additional effort. The FPR is controlled by the fingerprint size, where larger fingerprints lead to smaller FPRs. Different filter types in this class differ in their hash collision resolution strategies. For example, Cuckoo filters resolve collisions using Cuckoo hashing [ 27 , 11 ] and Vector Quotient filters use ideas from Robin Hood hashing [ 28 ] . If the whole key set is known in advance, static filters, such as XOR filters [ 15 ] , (Bumped) Ribbon filters [ 8 , 7 ] or Binary Fuse filters [ 16 ] , achieve smaller overhead factors, but are not suitable for streaming applications where the key set K is usually not known in advance. The above filters, even the non-static ones, require knowledge of the cardinality n=|K| (or an accurate estimate

Read the complete text