EUVIMEDOpdag EUVIMED
Crossref

Dynamic Flat Filter: A Unified Framework for Scalable and Stable Fingerprint-Based Filters

Yang Du, Shankui Ji, He Huang, Yu-E Sun, Ge Gao, Guoju Gao

Proceedings of the ACM on Management of Data · 2026-05-18 · 4 (3) · 1-26

DOI: 10.1145/3802043 ↗

At a glance

Journal article in Proceedings of the ACM on Management of Data, published online on 2026-05-18. Written by Yang Du and 5 co-authors. 49 references. Funded by: National Natural Science Foundation of China.

AbstractBibliografiske oplysningerCiteRelated studies

Abstract (original language)

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.

Funding

  • National Natural Science Foundation of China

Cite

APA

Du, Y., Ji, S., Huang, H., Sun, Y., Gao, G., & Gao, G. (2026). Dynamic Flat Filter: A Unified Framework for Scalable and Stable Fingerprint-Based Filters. Proceedings of the ACM on Management of Data, 4(3), 1-26. https://doi.org/10.1145/3802043

Vancouver

Du Y, Ji S, Huang H, Sun Y, Gao G, Gao G. Dynamic Flat Filter: A Unified Framework for Scalable and Stable Fingerprint-Based Filters. Proceedings of the ACM on Management of Data. 2026;4(3):1-26. doi:10.1145/3802043

BibTeX
@article{Du2026,
  author = {Du, Yang and Ji, Shankui and Huang, He and Sun, Yu-E and Gao, Ge and Gao, Guoju},
  title = {Dynamic Flat Filter: A Unified Framework for Scalable and Stable Fingerprint-Based Filters},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {3},
  pages = {1--26},
  doi = {10.1145/3802043}
}
Start for free →