{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T18:02:37Z","timestamp":1780941757311,"version":"3.54.1"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T00:00:00Z","timestamp":1701993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"The Hong Kong Research Grants Council","award":["16202722"],"award-info":[{"award-number":["16202722"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,12,8]]},"abstract":"<jats:p>Designing a space-efficient data structure to answer membership queries while ensuring high accuracy and real-time response is a challenging task in the field of stream processing. Many techniques have been developed to answer these queries in a sliding windows manner. However, assuming the user will conduct the query with the presupposed window size is not always practical. In this paper, we introduce a novel data structure called Learned Cuckoo Filter (LCF). It can provide satisfactory results for the approximate membership query on data streams, regardless of the user-defined query windows. LCF operates by adaptively maintaining cuckoo filters with the assistance of a well-trained oracle that learned the frequency feature of the data within the stream. To further enhance memory utilization, we develop a compact version of LCF (denoted by LCF_C), which selectively removes redundant information to reduce space consumption without compromising query accuracy. Furthermore, we conduct a thorough theoretical analysis of query accuracy and provide detailed guidelines for optimal parameter selection (denoted by LCF_O). Extensive experimental studies on synthetic and real-world datasets demonstrate the superiority of the proposed methods in terms of both space consumption and accuracy. Compared to the state-of-the-art algorithms, LCF_O can reduce up to 61% of space cost at the same error level, and achieve up to 12\u00d7 improved accuracy with the same space cost.<\/jats:p>","DOI":"10.1145\/3626758","type":"journal-article","created":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T14:01:21Z","timestamp":1702389681000},"page":"1-26","source":"Crossref","is-referenced-by-count":7,"title":["A Learned Cuckoo Filter for Approximate Membership Queries over Variable-sized Sliding Windows on Data Streams"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6876-5059","authenticated-orcid":false,"given":"Yao","family":"Tian","sequence":"first","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7487-657X","authenticated-orcid":false,"given":"Tingyun","family":"Yan","sequence":"additional","affiliation":[{"name":"Guangzhou University, Guang Zhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2022-7387","authenticated-orcid":false,"given":"Ruiyuan","family":"Zhang","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3204-7949","authenticated-orcid":false,"given":"Kai","family":"Huang","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8639-4570","authenticated-orcid":false,"given":"Bolong","family":"Zheng","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, Wu Han, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6343-1455","authenticated-orcid":false,"given":"Xiaofang","family":"Zhou","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,12,12]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"AOL 2006. Web Search Query Logs. https:\/\/jeffhuang.com\/search_query_logs.html"},{"key":"e_1_2_1_2_1","unstructured":"CAIDA 2016. The CAIDA UCSD Anonymized Internet Traces. https:\/\/www.caida.org\/catalog\/datasets\/passive_dataset"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1224252.1224501"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2016.2548442"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350275"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1365815.1365816"},{"key":"e_1_2_1_8_1","volume-title":"Approximate Caches for Packet Classification","author":"Chang Francis","unstructured":"Francis Chang, Kang Li, and Wu-chang Feng. 2004. Approximate Caches for Packet Classification. In INFOCOM. IEEE, 2196--2207."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00400-6"},{"key":"e_1_2_1_10_1","volume-title":"The dynamic cuckoo filter","author":"Chen Hanhua","unstructured":"Hanhua Chen, Liangyi Liao, Hai Jin, and Jie Wu. 2017. The dynamic cuckoo filter. In ICNP. IEEE Computer Society, 1--10."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_12_1","unstructured":"Zhenwei Dai and Anshumali Shrivastava. 2020. Adaptive Learned Bloom Filter (Ada-BF): Efficient Utilization of the Classifier with Application to Real-Time Information Filtering on the Web. In NeurIPS."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398363"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589285"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142477"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536354.2536359"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/859716.859719"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2022.3151140"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2009.57"},{"key":"e_1_2_1_21_1","unstructured":"Chen-Yu Hsu Piotr Indyk Dina Katabi and Ali Vakilian. 2019. Learning-Based Frequency Estimation Algorithms. In ICLR (Poster). OpenReview.net."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1400123.1400125"},{"key":"e_1_2_1_23_1","volume-title":"Proteus: A Self-Designing Range Filter. In SIGMOD Conference. ACM, 1670--1684","author":"Knorr Eric R.","year":"2022","unstructured":"Eric R. Knorr, Baptiste Lemaire, Andrew Lim, Siqiang Luo, Huanchen Zhang, Stratos Idreos, and Michael Mitzenmacher. 2022. Proteus: A Self-Designing Range Filter. In SIGMOD Conference. ACM, 1670--1684."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Georgia Koloniari Nikos Ntarmos Evaggelia Pitoura and Dimitris Souravlias. 2011. One is enough: distributed filtering for duplicate elimination. In CIKM. ACM 433--442.","DOI":"10.1145\/2063576.2063643"},{"key":"e_1_2_1_25_1","volume-title":"The Case for Learned Index Structures. In SIGMOD Conference. ACM, 489--504","author":"Kraska Tim","year":"2018","unstructured":"Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. 2018. The Case for Learned Index Structures. In SIGMOD Conference. ACM, 489--504."},{"key":"e_1_2_1_26_1","volume-title":"Stable Cuckoo Filter for Data Streams","author":"Li Shangsen","unstructured":"Shangsen Li, Lailong Luo, Deke Guo, and Yawei Zhao. 2021. Stable Cuckoo Filter for Data Streams. In ICPADS. IEEE, 138--145."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407830"},{"key":"e_1_2_1_28_1","first-page":"2346","article-title":"Learning under Concept Drift","volume":"31","author":"Lu Jie","year":"2019","unstructured":"Jie Lu, Anjin Liu, Fan Dong, Feng Gu, Jo\u00e3o Gama, and Guangquan Zhang. 2019. Learning under Concept Drift: A Review. IEEE Trans. Knowl. Data Eng. 31, 12 (2019), 2346--2363.","journal-title":"A Review. IEEE Trans. Knowl. Data Eng."},{"key":"e_1_2_1_29_1","volume-title":"Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores. In SIGMOD Conference. ACM","author":"Luo Siqiang","year":"2020","unstructured":"Siqiang Luo, Subarna Chatterjee, Rafael Ketsetsidis, Niv Dayan, Wilson Qin, and Stratos Idreos. 2020. Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores. In SIGMOD Conference. ACM, 2071--2086."},{"key":"e_1_2_1_30_1","volume-title":"Ravishankar","author":"Majumdar Saugat","year":"2007","unstructured":"Saugat Majumdar, Dhananjay Kulkarni, and Chinya V. Ravishankar. 2007. Addressing Click Fraud in Content Delivery Systems. In INFOCOM. IEEE, 240--248."},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Ahmed Metwally Divyakant Agrawal and Amr El Abbadi. 2005. Duplicate detection in click streams. In WWW. ACM 12--21.","DOI":"10.1145\/1060745.1060753"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Michael Mitzenmacher. 2018. A Model for Learned Bloom Filters and Optimizing by Sandwiching. In NeurIPS. 462--471.","DOI":"10.1007\/978-1-4614-8265-9_751"},{"key":"e_1_2_1_33_1","volume-title":"Baraniuk","author":"Mousavi Ali","year":"2015","unstructured":"Ali Mousavi, Ankit B. Patel, and Richard G. Baraniuk. 2015. A deep learning approach to structured signal recovery. In Allerton. IEEE, 1336--1343."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0007-9"},{"key":"e_1_2_1_35_1","volume-title":"How to Approximate a Set without Knowing Its Size in Advance","author":"Pagh Rasmus","unstructured":"Rasmus Pagh, Gil Segev, and Udi Wieder. 2013. How to Approximate a Set without Knowing Its Size in Advance. In FOCS. IEEE Computer Society, 80--89."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183737"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"David M. W. Powers. 1998. Applications and Explanations of Zipf's Law. In CoNLL. ACL 151--160.","DOI":"10.3115\/1603899.1603924"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-008-9192-1"},{"key":"e_1_2_1_39_1","volume-title":"Age-Partitioned Bloom Filters. CoRR abs\/2001.03147","author":"Shtul Ariel","year":"2020","unstructured":"Ariel Shtul, Carlos Baquero, and Paulo S\u00e9rgio Almeida. 2020. Age-Partitioned Bloom Filters. CoRR abs\/2001.03147 (2020)."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10586-016-0567-8"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529347"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364333"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2021.3067713"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/1685872.1685986"},{"key":"e_1_2_1_45_1","volume-title":"The Logarithmic Dynamic Cuckoo Filter","author":"Zhang Fan","unstructured":"Fan Zhang, Hanhua Chen, Hai Jin, and Pedro Reviriego. 2021. The Logarithmic Dynamic Cuckoo Filter. In ICDE. IEEE, 948--959."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196931"},{"key":"e_1_2_1_47_1","volume-title":"The Stair Sketch: Bringing more Clarity to Memorize Recent Events","author":"Zhao Yikai","unstructured":"Yikai Zhao, Yubo Zhang, Pu Yi, Tong Yang, Bin Cui, and Steve Uhlig. 2022. The Stair Sketch: Bringing more Clarity to Memorize Recent Events. In ICDE. IEEE, 164--177."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626758","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626758","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T13:03:19Z","timestamp":1755867799000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626758"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,8]]},"references-count":47,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12,8]]}},"alternative-id":["10.1145\/3626758"],"URL":"https:\/\/doi.org\/10.1145\/3626758","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,8]]}}}