  We introduce the adaptive cuckoo filter (ACF), a data structure for
approximate set membership that extends cuckoo filters by reacting to false
positives, removing them for future queries. As an example application, in
packet processing queries may correspond to flow identifiers, so a search for
an element is likely to be followed by repeated searches for that element.
Removing false positives can therefore significantly lower the false positive
rate. The ACF, like the cuckoo filter, uses a cuckoo hash table to store
fingerprints. We allow fingerprint entries to be changed in response to a false
positive in a manner designed to minimize the effect on the performance of the
filter. We show that the ACF is able to significantly reduce the false positive
rate by presenting both a theoretical model for the false positive rate and
simulations using both synthetic data sets and real packet traces.
