Conditional Cuckoo Filters
ACM SIGMOD 2021, June 20-25, 2021, Xi'an, Shaanxi, China
Bloom filters, cuckoo filters, and other approximate set membership sketches have a wide range of applications. Oftentimes, expensive operations can be skipped if an item is not in a data set. These filters provide an inexpensive, memory-efficient way to test if an item is in a set and avoid unnecessary operations. Existing sketches only allow membership testing for a single set. However, in some applications such as join processing, the relevant set is not fixed and is determined by a set of predicates.
We propose the Conditional Cuckoo Filter, a simple modification of the cuckoo filter that allows for set membership testing given predicates on a pre-computed sketch. This filter also introduces a novel chaining technique that enables cuckoo filters to handle the insertion of duplicate keys. We evaluate our methods on a join processing application and show that they significantly reduce the number of tuples that a join must process
Auteur(s)