The Logarithmic Dynamic Cuckoo Filter
Fan Zhang, Hanhua Chen, Hai Jin, Pedro Reviriego
Abstract
The emergence of big data applications makes efficient representation for large-scale dynamic data sets a challenge. The state-of-the-art design, i.e., the dynamic cuckoo filter (DCF), provides extensible approximate set representation by employing a novel chain based data structure which allows appending new building cuckoo filter blocks. However, such a design needs linearly increasing computation costs and memory space when a set scales. This makes it inefficient for big data sets. In this paper, we propose a novel data structure for dynamic big data sets, called logarithmic dynamic cuckoo filter (LDCF). LDCF uses a novel multi-level tree structure and reduces the worst insertion and membership testing times from O(N) to O(1), where N is the size of the set. At the same time, LDCF reduces the memory cost of DCF as the cardinality of the set increases. Comprehensive experiment results show that LDCF significantly reduces the membership checking time and the memory space cost for large-scale datasets compared to state-of-the-art designs.
Ask Lune
Know where this paper stands in minutes, not an afternoon.
Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.
4 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
its abstract · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers4
- InfiniFilter: Expanding Filters to Infinity and BeyondNiv Dayan, Ioana O. Bercea, Pedro Reviriego, Rasmus PaghSIGMOD 2023 · 27 citations
- Adaptive Online Cache Capacity Optimization via Lightweight Working Set Size Estimation at ScaleRong Gu, Simian Li, Haipeng Dai, Hancheng Wang et al.USENIX ATC 2023 · 17 citations
- Aleph Filter: To Infinity in Constant TimeNiv Dayan, Ioana Oriana Bercea, Rasmus PaghVLDB 2024 · 13 citations
- Zeno Filter: To Infinity in Tiny StepsHyuhng Min Kim, Navid Eslami, Niv DayanSIGMOD 2026 · 2 citations
Related papers
- A Learned Cuckoo Filter for Approximate Membership Queries over Variable-sized Sliding Windows on Data StreamsYao Tian, Tingyun Yan, Ruiyuan Zhang, Kai Huang et al.SIGMOD 2024 · 7 citations
- Dynamic Flat Filter: A Unified Framework for Scalable and Stable Fingerprint-Based FiltersYang Du, Shankui Ji, He Huang, Yu-E Sun et al.SIGMOD 2026
- CuckooGraph: A Scalable and Space-Time Efficient Data Structure for Large-Scale Dynamic GraphsZhuochen Fan, Yalun Cai, Zirui Liu, Jiarui Guo et al.ICDE 2025 · 3 citations
- Prefix Filter: Practically and Theoretically Better Than BloomTomer Even, Guy Even, Adam MorrisonVLDB 2022 · 13 citations
- Vacuum Filters: More Space-Efficient and Faster Replacement for Bloom and Cuckoo FiltersMinmei Wang, Mingxun Zhou, Shouqian Shi, Chen QianVLDB 2020 · 58 citations
