  Adaptive filters, such as telescoping and adaptive cuckoo filters, update
their representation upon detecting a false positive to avoid repeating the
same error in the future. Adaptive filters require an auxiliary structure,
typically much larger than the main filter and often residing on slow storage,
to facilitate adaptation. However, existing adaptive filters are not practical
and have seen no adoption in real-world systems due to two main reasons.
Firstly, they offer weak adaptivity guarantees, meaning that fixing a new false
positive can cause a previously fixed false positive to come back. Secondly,
the sub-optimal design of the auxiliary structure results in adaptivity
overheads so substantial that they can actually diminish the overall system
performance compared to a traditional filter.
  In this paper, we design and implement AdaptiveQF, the first practical
adaptive filter with minimal adaptivity overhead and strong adaptivity
guarantees, which means that the performance and false-positive guarantees
continue to hold even for adversarial workloads. The AdaptiveQF is based on the
state-of-the-art quotient filter design and preserves all the critical features
of the quotient filter such as cache efficiency and mergeability. Furthermore,
we employ a new auxiliary structure design which results in considerably low
adaptivity overhead and makes the AdaptiveQF practical in real systems.
