Fingerprint-based filters, such as Cuckoo and Quotient Filters, are a key class of data structures for approximate membership query with deletion support. However, their fixed capacity is a major limitation in dynamic environments with unpredictable data volumes. While prior research has introduced dynamic filters, their resizing mechanisms are tightly coupled to specific filter structures, making their mechanisms difficult to generalize. Moreover, prior dynamic solutions introduce severe performance bottlenecks: chain-based or ring-based filters enable incremental growth yet degrade queries by probing multiple sub-filters, while global-resizing filters cause long, disruptive stalls during resizing as their single, large filter grows. In addition, prior incremental designs often leave scale-induced false positive rate growth unaddressed. In this paper, we present the Dynamic Flat Filter (DFF), a unified framework that decouples dynamic resizing from core filter logic, enabling fingerprint-based filters to achieve incremental scalability while preserving their original performance, memory efficiency, and false positive guarantees. DFF maintains a variable-sized set of independent segments, each reusing the base filter's native layout, enabling fine-grained resizing with only minor integration hooks. We achieve O(1) insertion, query, and deletion by employing a flat structure for all segments and a lookup table that quickly maps any item to its corresponding segment. Additionally, DFF incorporates a fingerprint growth strategy that keeps the false positive rate essentially constant as the filter scales. We demonstrate the general applicability of DFF by integrating it with Cuckoo and Quotient Filters, each requiring fewer than 60 lines of code to be modified, and evaluate these implementations on real-world and synthetic datasets. Experimental results show that DFF outperforms SOTA baselines in insertion, query, and deletion, maintains high memory efficiency, and stabilizes the false positive rate. Notably, DFF attains at least 1.33× the overall throughput on query-intensive workloads and reduces worst-case insertion latency by up to 59.5% compared with the best prior dynamic filter.
Du et al. (Mon,) studied this question.