Cuckoo Filter: Practically Better Than Bloom
The DOI matches its Crossref record; 28 of the 30 references it cites were found in a registry or an index.
Abstract
In many networking systems, Bloom filters are used for high-speed set membership tests. They permit a small fraction of false positive answers with very good space efficiency. However, they do not permit deletion of items from the set, and previous attempts to extend "standard" Bloom filters to support deletion all degrade either space or performance.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Space/time trade-offs in hash coding with allowable errors
Bloom, B. H. (1970) · Communications of the ACM · doi:10.1145/362686.362692 · Cited by 7,492
Network Applications of Bloom Filters: A Survey
Broder, A., & Mitzenmacher, M. (2004) · Internet Mathematics · doi:10.1080/15427951.2004.10129096 · Cited by 1,991
Self-citationSummary cache: a scalable wide-area Web cache sharing protocol
Fan, L., Cao, P., Almeida, J., & Broder, A. Z. (2000) · IEEE/ACM Transactions on Networking · doi:10.1109/90.851975 · Cited by 1,811
Pagh, R., & Rodler, F. F. (2004) · Journal of Algorithms · doi:10.1016/j.jalgor.2003.12.002 · Cited by 1,045
LIPSIN: line speed publish/subscribe inter-networking
Jokela, P., Zahemszky, A., Esteve Rothenberg, C., Arianfar, S., & Nikander, P. (2009) · Proceedings of the ACM SIGCOMM 2009 conference on Data communication · doi:10.1145/1592568.1592592 · Cited by 434
The Power of Two Random Choices: A Survey of Techniques and Results
Mitzenmacher, M., Richa, A. W., & Sitaraman, R. (2001) · Combinatorial Optimization · doi:10.1007/978-1-4615-0013-1_9 · Cited by 431
Self-citationSummary cache: a scalable wide-area Web cache sharing protocol
Fan, L., Cao, P., Almeida, J., & Broder, A. Z. (1998) · Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication · doi:10.1145/285237.285287 · Cited by 422
An Improved Construction for Counting Bloom Filters
Bonomi, F., Mitzenmacher, M., Panigrahy, R., Singh, S., & Varghese, G. (2006) · Lecture Notes in Computer Science · doi:10.1007/11841036_61 · Cited by 383
Self-citationFast hash table lookup using extended bloom filter: an aid to network processing
Song, H., Dharmapurikar, S., Turner, J., & Lockwood, J. (2005) · Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications · doi:10.1145/1080091.1080114 · Cited by 328
The Bloomier filter: an efficient data structure for static support lookup tables
Chazelle, B., Kilian, J., Rubinfeld, R., & Tal, A. (2004) · doi:10.5555/982792.982797 · Cited by 327
Research works printed but not linked: 3
- 10.5555/2133036.2133129 · doi:10.5555/2133036.2133129
- 10.1002/rsa.v33:2 · doi:10.1002/rsa.v33:2
- 10.5555/1768570.1768582 · doi:10.5555/1768570.1768582
Cited by
Items 901–946 of 946
Lee, D., Lee, S., Joo, Y., Nam, K., & Paek, Y. (2026) · IEEE Access · doi:10.1109/access.2026.3701023
ZOR Filters: Fast and Smaller Than Fuse Filters
Limasset, A. (2026) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.sea.2026.24
Guarded Epoch Bloom Filters for Sliding-Window MembershipPreprint
Alpay, F., & Sarioğlu, L. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2606.19210
Hash Table Design for RDMA:Challenges and OpportunitiesPreprint
She, S., & Dai, H. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2606.24073
Benchmarking Column Statistics for Analytical Query Pruning
Pedersen, A. B., Yousefzadeh-Asl-Miandoab, E., Oukid, I., & Hentschel, M. (2026) · International Workshop on Testing Database Systems · doi:10.1145/3810991.3811633
Architectures for Secure and Deployable In-Network Caching in Encrypted Content Delivery Systems
Korçak, Ö., & Bayrak, G. (2026) · International Journal of Advances in Engineering and Pure Sciences · doi:10.7240/jeps.1827700
A comprehensive survey on multi-GPU systems
Gheibi-Fetrat, A., Maleki, A., Zoufan, S., Mohammadi-Lak, M., Ahmadi-Tonekaboni, A., Alinejad, M., Yahyazadeh, K., Alizadeh, M., Akbarzadeh, N., Darabi-moghaddam, S., et al. (2026) · Parallel Computing · doi:10.1016/j.parco.2026.103208
Efficient Hash-to-Index via Rejection Sampling for Online Fault Detection with Bloom/Cuckoo Filters
Cishugi, E. S., Chen, K.-H., & Ottavi, M. L. (2026) · IEEE European Test Symposium (ETS) · doi:10.1109/ets69887.2026.11591729
Probabilistic data structures for blockchain miners in delay sensitive IoT applications: a review
Miglani, A., Kumar, N., Budhiraja, I., Khan, H., Jabbari, A., & Shankar, A. (2026) · Cluster Computing · doi:10.1007/s10586-026-06264-w
Genome misassembly detection using Stash: A data structure based on stochastic tile hashing
Sarvar, A., Coombe, L., & Birol, İ. (2026) · PLoS ONE · doi:10.1371/journal.pone.0333729
Tian, Q., Zhang, P., & Zou, Q. (2026) · Lecture notes in computer science · doi:10.1007/978-981-92-3498-1_30
Yüce, M. F. (2026) · Computers & Security · doi:10.1016/j.cose.2026.105047
STEM 2 : A Fast and Space-efficient Data Structure for Exact Multi-Set Membership Queries
Yannian, N., Song, H., & Minmei, W. (2026) · Proceedings of the VLDB Endowment · doi:10.14778/3819518.3819561
Streaming Data Linkage and Analytics
Vatsalan, D., Asghar, H., & Kâafar, M. A. (2026) · Advances in information security · doi:10.1007/978-3-032-21932-9_12
Laohajirapan, A., & Rattanavipanon, N. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2607.23698
Efficient data replication for large-scale systems
Palma, T. F. M. (2026) · Portuguese National Funding Agency for Science, Research and Technology (RCAAP Project by FCT)
Reducing Page Faults via Invalidation-Based Mapping Propagation in Multi-GPU Systems
KIM, J., Ha, D., Kim, S., Cho, W., Kim, S., Ding, Y., & Ro, W. W. (2026) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1109/isca66397.2026.00110
C2P-Cache: Scalable GPU L1 Cache Sharing via Concurrent Candidate PruningPreprint
Li, H., Wu, L., Li, T., Ma, S., Xun, H., Zhang, J., Tang, Y., Tang, J., & Xie, X. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2608.00412
BRAV: Blockchain-Enabled Revocable Authentication for UAV-Assisted Internet of Vehicles
Wang, J., Xu, C. L., Zhu, L., Ke, X., & Liu, X. (2026) · IEEE Transactions on Cloud Computing · doi:10.1109/tcc.2026.3720306
Chen, X., Lin, Z., Liao, L., Zhu, L., Zheng, L., Yu, J., Liu, Y., Su, J., Xu, Y., Yao, P., et al. (2026) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3770855.3817702
Rangereduce: Query-Driven LSM Compactions
Kaushik, S., Athanassoulis, M., & Sarkar, S. (2026) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde65706.2026.00194
MVX-CF: A Multi-Value eXpandable Cuckoo Filter for Pending Interest Tables in Named Data Networking
Lee, J., & Byun, H. (2026) · IEEE Access · doi:10.1109/access.2026.3723791
Lifecycle-Aware Archival for Asymmetric Financial Datasets: A Production StudyPreprint
Manek, T. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2608.12367
CavityRank: Zero-Extra-Byte Residual Routing for Cuckoo FiltersPreprint
Guan, Y. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2608.13970
High-Performance and Cache-Efficiency Adaptive Radix Tree for Disaggregated Memory
Zhang, B., Zheng, S., Li, J., Shu, S., Qi, Z., Huang, L., & Mei, H. (2026) · IEEE Transactions on Computers · doi:10.1109/tc.2026.3726609
Biphasic Sketch: Multi-Attribute Stream Summarization for Arbitrary Attribute Combinations
Zhang, N., Luo, L., Wei, Z., Zhang, Q., Li, Y., & Guo, D. (2026) · International Workshop on Quality of Service · doi:10.1109/iwqos70441.2026.11661276
Time-Efficient Target Tag Information Collection in Commodity RFID Systems
Wang, Y., Cao, Z., Qu, Z., Liu, J., Tang, B., & Ye, B. (2026) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2026.3728867
Diva++: Dynamic Range Filtering over Hard WorkloadsPreprint
Eslami, N., Bercea, I. O., & Dayan, N. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2608.27616
Wildcard-Aware Topic Management Using a Bloom Filter for Distributed MQTT Brokers
Banno, R., & Watanabe, Y. (2026) · IEEE Internet of Things Journal · doi:10.1109/jiot.2026.3729670
Efficient, Adaptable, and Scalable Synopses for Data-Intensive Systems
Ngo, Q. V. (2026) · Chalmers Research (Chalmers University of Technology)
Ada-Jelly: A Lightweight and Adaptive Subflow Sketch for High-Speed Network Monitoring
Lin, Z., Si, X., Zhang, D., Liu, H., Xiao, B., Li, M., Zhang, J., Wu, C., & Chen, X. (2026) · IEEE International Conference on Web Services (ICWS) · doi:10.1109/icws72778.2026.00047
Xiaoyuan, G. O. N. G., Zhong, J., Zeng, Z., & Han, F. (2026) · Xibei Gongye Daxue Xuebao/Journal of Northwestern Polytechnical University · doi:10.1051/jnwpu/20264430538
Detection of password reuse and credential stuffing: a server-side approach
Mishra, A., Konduru, S. S., Mishra, S., & Panday, S. (2026) · Scientific Reports · doi:10.1038/s41598-026-71089-x
AI-Driven Self-Healing System for Real-Time Software Incident Management
Vijaya Lakshmi, G., & Aparna, S. (2026) · International Journal for Research in Applied Science and Engineering Technology · doi:10.22214/ijraset.2026.84917
He, H., Xu, Q., Yu, H. C., Nie, L., & Lu, J. (2026) · IEEE Transactions on Network and Service Management · doi:10.1109/tnsm.2026.3738578
F4RM: Feature-Restricted Round-Robin Random Mapping for Weightless Neural Networks
Martins, L., Burock, H., Richards, J., de Araújo, L. S., Lima, P. M. V., & de Farias, C. M. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-39895-6_19
Super Bloom: Fast and Precise Filter for Streaming k -Mer Queries
Conchon-Kerjan, E., Rouzé, T., Robidou, L., Ingels, F., & Limasset, A. (2026) · Journal of Computational Biology · doi:10.1177/15578666261493564
Bansal, A. (2026) · International Journal of Scientific Research in Science Engineering and Technology · doi:10.32628/ijsrset2613533
Crafted Innocence: A Stigmatization Threat Model for Watchlist Screening and Its Defenses
Gao, R., & Yan, H. (2026) · Lecture notes in computer science · doi:10.1007/978-981-92-6857-3_34
KVCompass: A Discovery Plane for Internet-Scale Prefix Cache Sharing in LLM ServingPreprint
Ling, S., Fang, F., & Qian, C. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2610.24179
SPiRiT: Verifiable Contact Tracing for Balanced Security, Privacy, and Safety
Rabaninejad, R., Abtahi, A., Michalas, A., & Aminifar, A. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-36874-4_4
Proba: A High-Performance, Low-Traffic Probabilistic Spatial Memory Streaming PrefetcherPreprint
Huang, Y., Wong, J., & Ainsworth, S. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2610.30448
Fresh-Priority Eviction for Cuckoo Filters: Exploiting Latent Randomness Under XOR HashingPreprint
Liu, M. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2611.01599
Toward space-optimal approximate colored indexes at scalePreprint
Okcu, T., Alkan, C., & Limasset, A. (2026) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.64898/2026.11.05.764633
Robust and Efficient Privacy-Preserving User-Device Authentication in Edge Computing
Zhang, Z., Zhang, Y., Pang, Y., Di, H., Yuan, H., & Cao, J. (2026) · IEEE International Conference on Privacy Computing and Data Security (PCDS) · doi:10.1109/pcds70463.2026.00043
Incremental Keyword Private Information Retrieval from d-ary Segmented Cuckoo Filters
Ninh, Q.-B. (2026) · Lecture notes in computer science · doi:10.1007/978-981-92-7776-6_10
Metadata
- Authors
- Fan, B., Andersen, D. G., Kaminsky, M., & Mitzenmacher, M. D.
- Affiliations
- Carnegie Mellon University (US)
- Intel (United States) (US)
- Harvard University (US)
- Venue
- Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies
- Publisher
- ACM
- Published
- 2014-12-02
- Pages
- 75-88
- OpenAlex
- W1967373117
- Cited by
- 737
- References
- 30
- Citations by year
- 2026: 55 · 2025: 78 · 2024: 90 · 2023: 85 · 2022: 79 · 2021: 83 · 2020: 79 · 2019: 81 · 2018: 49 · 2017: 35 · 2016: 14 · 2015: 8 · 2014: 1
- FWCI
- 11.39
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- ACM International Conference on emerging Networking EXperiments and Technologies (CoNEXT) (publishedVersion)
- Funders
- Division of Computer and Network Systems (CCF-0964474, CNS-1040801, CCF-1320231, CNS-1228598, and IIS-0964473)
- Division of Computing and Communication Foundations (CCF-0964474, CNS-1040801, CCF-1320231, CNS-1228598, and IIS-0964473)
- Division of Information and Intelligent Systems (CCF-0964474, CNS-1040801, CCF-1320231, CNS-1228598, and IIS-0964473)
- Topics
- Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
- Physical Sciences › Computer Science › Hardware and Architecture › Network Packet Processing and Optimization
- Physical Sciences › Computer Science › Information Systems › Advanced Database Systems and Queries
- Keywords
- cuckoo filter, Bloom filter, false positives, space efficiency, data structures
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.