Medury, Altarawneh, and Skjellum Receive Certificate of Best Paper

The approximate set-membership data structures (ASMDS), like the Bloom filter and cuckoo filter, provide constant-time testing of set-membership. They produce false positives because of a loss of bits during compression. However, in case all potential false positives are known (or can be evaluated), it is possible to use filter cascades and collectively eliminate such false positives. The application of the filter cascading algorithm to the Bloom filter was originally proposed for optimizing memory usage and is currently an integral part of CRLLite.

Recently, the proposed cuckoo filters function similarly to Bloom filters but with cuckoo hashing techniques. They produce comparatively lower storage overheads and additionally support efficient deletions. Therefore, applying the cascading algorithms to the cuckoo filter will also produce lower storage overheads in comparison to cascading Bloom filters. Further, the cuckoo filter’s support for deletions enables efficient updates to the filter cascades.

In this paper, we present the design and analysis of cascading cuckoo filters, a potentially more space-optimal ASMDS in comparison to cascading Bloom filters. A novel contribution of this paper is the application of the filter cascading algorithm to the cuckoo filter, which has not been proposed before to the best of our knowledge.