{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:58:13Z","timestamp":1781326693789,"version":"3.54.1"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,9,22]]},"abstract":"<jats:p>Estimating item frequencies in data streams is a fundamental task that supports a wide range of applications. To improve accuracy, existing algorithms typically employ filters to handle cold (infrequent) and hot (frequent) items separately. However, their accuracy often degrades across different data streams due to fixed parameter settings. Once the filter reaches its capacity, it can no longer effectively distinguish target items, resulting in a significant drop in accuracy. To achieve higher accuracy and better adaptability to data streams, we propose SieveSketch, a novel framework for frequency estimation in data stream processing. Inspired by two observations of narrow cold-item frequency range and different sensitivity of items to hash collisions, SieveSketch proposes adaptive scaling to adjust the count range of each counter with few bits (e.g. 4 bits) to record massive cold items efficiently, and takes a frequency-oriented counting method to process items at a more fine-grained level to improve the accuracy. We theoretically analyze the error bound of SieveSketch. We conduct extensive experiments on real-world and synthetic datasets, and the results show that, compared to the state-of-the-art, SieveSketch reduces the estimation error by up to 222.1 times.<\/jats:p>","DOI":"10.1145\/3749182","type":"journal-article","created":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T17:17:03Z","timestamp":1758647823000},"page":"1-25","source":"Crossref","is-referenced-by-count":0,"title":["SieveSketch: A Fine-grained and Adaptive Sketch Framework for Accurate Frequency Estimation"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-4034-8695","authenticated-orcid":false,"given":"Shishi","family":"Zhang","sequence":"first","affiliation":[{"name":"Xiamen Key Laboratory of Intelligent Storage and Computing, School of Informatics, Xiamen University, Xiamen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-0549-7051","authenticated-orcid":false,"given":"Yaping","family":"Xu","sequence":"additional","affiliation":[{"name":"Laboratory of Intelligent Storage and Computing, School of Informatics, Xiamen University, Xiamen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2923-6247","authenticated-orcid":false,"given":"Lu","family":"Tang","sequence":"additional","affiliation":[{"name":"Laboratory of Intelligent Storage and Computing, School of Informatics, Xiamen University, Xiamen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,9,23]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"MAWI Working Group Archive. 2023. http:\/\/mawi.nezu.wide.ad.jp\/mawi\/."},{"key":"e_1_2_1_2_1","first-page":"1","article-title":"Randomized admission policy for efficient top-k and frequency estimation","author":"Ben-Basat Ran","year":"2016","unstructured":"Ran Ben-Basat, Gil Einziger, Roy Friedman, and Yaron Kassner. 2016. Randomized admission policy for efficient top-k and frequency estimation. In Proc. of IEEE INFOCOM. 1-9.","journal-title":"Proc. of IEEE INFOCOM."},{"key":"e_1_2_1_3_1","first-page":"267","article-title":"Network Traffic Characteristics of Data Centers in the Wild","author":"Benson Theophilus","year":"2010","unstructured":"Theophilus Benson, Aditya Akella, and David A Maltz. 2010. Network Traffic Characteristics of Data Centers in the Wild. In Proc. of ACM SIGCOMM. 267-280.","journal-title":"Proc. of ACM SIGCOMM."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_5_1","unstructured":"CAIDA. 2019. http:\/\/www.caida.org\/ data\/overview\/."},{"key":"e_1_2_1_6_1","first-page":"693","article-title":"Finding Frequent Items in Data Streams","author":"Charikar Moses","year":"2002","unstructured":"Moses Charikar, Kevin Chen, and Martin Farach-Colton. 2002. Finding Frequent Items in Data Streams. In Proc. of Springer ICALP. 693-703.","journal-title":"Proc. of Springer ICALP."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_8_1","first-page":"1629","article-title":"Mahout: Low-overhead datacenter traffic management using end-host-based elephant detection","author":"Curtis Andrew R","year":"2011","unstructured":"Andrew R Curtis, Wonho Kim, and Praveen Yalagandula. 2011. Mahout: Low-overhead datacenter traffic management using end-host-based elephant detection. In Proc. of IEEE INFOCOM. 1629-1637.","journal-title":"Proc. of IEEE INFOCOM."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/964725.633056"},{"key":"e_1_2_1_10_1","first-page":"1093","article-title":"Sketch algorithms for estimating point queries in nlp","author":"Goyal Amit","year":"2012","unstructured":"Amit Goyal, Hal Daume Iii, and Graham Cormode. 2012. Sketch algorithms for estimating point queries in nlp. In Proc. of EMNLP. 1093-1103.","journal-title":"Proc. of EMNLP."},{"key":"e_1_2_1_11_1","first-page":"535","article-title":"A web page prediction model based on click-stream tree representation of user behavior","author":"G\u00fcnd\u00fcz \u015eule","year":"2003","unstructured":"\u015eule G\u00fcnd\u00fcz and M Tamer \u00d6zsu. 2003. A web page prediction model based on click-stream tree representation of user behavior. In Proc. of ACM SIGKDD. 535-540.","journal-title":"Proc. of ACM SIGKDD."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00156"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2534169.2486012"},{"key":"e_1_2_1_14_1","first-page":"804","article-title":"LogLog Filter: Filtering Cold Items within a Large Range over High Speed Data Streams","author":"Jia Peng","year":"2021","unstructured":"Peng Jia, Pinghui Wang, Junzhou Zhao, Ye Yuan, Jing Tao, and Xiaohong Guan. 2021. LogLog Filter: Filtering Cold Items within a Large Range over High Speed Data Streams. In Proc. of IEEE ICDE. 804-815.","journal-title":"Proc. of IEEE ICDE."},{"key":"e_1_2_1_15_1","first-page":"591","article-title":"What is Twitter, a social network or a news media?","author":"Kwak Haewoon","year":"2010","unstructured":"Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. 2010. What is Twitter, a social network or a news media?. In Proc. of ACM WWW. 591-600.","journal-title":"Proc. of ACM WWW."},{"key":"e_1_2_1_16_1","first-page":"273","article-title":"F2FS: A new file system for flash storage","author":"Lee Changman","year":"2015","unstructured":"Changman Lee, Dongho Sim, Jooyoung Hwang, and Sangyeun Cho. 2015. F2FS: A new file system for flash storage. In Proc. of USENIX FAST. 273-286.","journal-title":"Proc. of USENIX FAST."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_18_1","first-page":"1574","article-title":"WavingSketch","author":"Li Jizhou","year":"2020","unstructured":"Jizhou Li, Zikun Li, Yifei Xu, Shiqi Jiang, Tong Yang, Bin Cui, Yafei Dai, and Gong Zhang. 2020. WavingSketch: An Unbiased and Generic Sketch for Finding Top-k Items in Data Streams. In Proc. of ACM SIGKDD. 1574-1584.","journal-title":"In Proc. of ACM SIGKDD."},{"key":"e_1_2_1_19_1","first-page":"1","article-title":"LadderFilter","author":"Li Yuanpeng","year":"2023","unstructured":"Yuanpeng Li, Feiyu Wang, Xiang Yu, Yilong Yang, Kaicheng Yang, Tong Yang, Zhuo Ma, Bin Cui, and Steve Uhlig. 2023. LadderFilter: Filtering Infrequent Items with Small Memory and Time Overhead. In Proc. of ACM SIGMOD. 1-21.","journal-title":"In Proc. of ACM SIGMOD."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2023.3316426"},{"key":"e_1_2_1_21_1","first-page":"101","article-title":"One Sketch to Rule Them All","author":"Liu Zaoxing","year":"2016","unstructured":"Zaoxing Liu, Antonis Manousis, Gregory Vorsanger, Vyas Sekar, and Vladimir Braverman. 2016. One Sketch to Rule Them All: Rethinking Network Flow Monitoring with UnivMon. In Proc. of ACM SIGCOMM. 101-114.","journal-title":"Rethinking Network Flow Monitoring with UnivMon. In Proc. of ACM SIGCOMM."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1384529.1375472"},{"key":"e_1_2_1_23_1","unstructured":"Claudio Lucchese Salvatore Orlando Raffaele Perego and Fabrizio Silvestri. 2023. Real-life transactional dataset. http:\/\/fimi.uantwerpen.be\/data\/."},{"key":"e_1_2_1_24_1","first-page":"173","article-title":"Identifying frequent items in sliding windows over on-line packet streams","author":"Lukasz G.","year":"2003","unstructured":"G. Lukasz, D. David, D. Erik D, L. Alejandro, and M. J Ian. 2003. Identifying frequent items in sliding windows over on-line packet streams. In Proc. of ACM IMC. 173-178.","journal-title":"Proc. of ACM IMC."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3625054.3625065"},{"key":"e_1_2_1_26_1","first-page":"398","article-title":"Efficient Computation of Frequent and Top-k Elements in Data Streams","author":"Metwally Ahmed","year":"2005","unstructured":"Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi. 2005. Efficient Computation of Frequent and Top-k Elements in Data Streams. In Proc. of Springer ICDT. 398-412.","journal-title":"Proc. of Springer ICDT."},{"key":"e_1_2_1_27_1","first-page":"151","article-title":"Applications and explanations of Zipf's law","author":"Powers David MW","year":"1998","unstructured":"David MW Powers. 1998. Applications and explanations of Zipf's law. In Proc. of ACL EMNLP-CoNLL., 151-160.","journal-title":"Proc. of ACL EMNLP-CoNLL."},{"key":"e_1_2_1_28_1","first-page":"1449","article-title":"Augmented Sketch","author":"Roy Pratanu","year":"2016","unstructured":"Pratanu Roy, Arijit Khan, and Gustavo Alonso. 2016. Augmented Sketch: Faster and More Accurate Stream Processing. In Proc. of ACM SIGMOD. 1449-1463.","journal-title":"Faster and More Accurate Stream Processing. In Proc. of ACM SIGMOD."},{"key":"e_1_2_1_29_1","first-page":"164","article-title":"Heavy-Hitter Detection Entirely in the Data Plane","author":"Sivaraman Vibhaalakshmi","year":"2017","unstructured":"Vibhaalakshmi Sivaraman, Srinivas Narayana, Ori Rottenstreich, Shan Muthukrishnan, and Jennifer Rexford. 2017. Heavy-Hitter Detection Entirely in the Data Plane. In Proc. of ACM SOSR. 164-176.","journal-title":"Proc. of ACM SOSR."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386367.3432729"},{"key":"e_1_2_1_31_1","unstructured":"The source code and appendix of our algorithm. 2024. https:\/\/github.com\/aGGCat\/SeiveSketch.git."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2019.8737499"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compind.2020.103257"},{"key":"e_1_2_1_34_1","first-page":"241","article-title":"You Are How You Click","author":"Wang Gang","year":"2013","unstructured":"Gang Wang, Tristan Konolige, Christo Wilson, Xiao Wang, Haitao Zheng, and Ben Y Zhao. 2013. You Are How You Click: Clickstream Analysis for Sybil Detection. In Proc. of USENIX Security. 241-256.","journal-title":"Clickstream Analysis for Sybil Detection. In Proc. of USENIX Security."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/78922.78925"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2556661"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2019.2923772"},{"key":"e_1_2_1_38_1","first-page":"2584","article-title":"HeavyGuardian","author":"Yang Tong","year":"2018","unstructured":"Tong Yang, Junzhi Gong, Haowei Zhang, Lei Zou, Lei Shi, and Xiaoming Li. 2018a. HeavyGuardian: Separate and Guard Hot Items in Data Streams. In Proc. of ACM SIGKDD. 2584-2593.","journal-title":"Separate and Guard Hot Items in Data Streams. In Proc. of ACM SIGKDD."},{"key":"e_1_2_1_39_1","first-page":"561","article-title":"Elastic Sketch","author":"Yang Tong","year":"2018","unstructured":"Tong Yang, Jie Jiang, Peng Liu, Qun Huang, Junzhi Gong, Yang Zhou, Rui Miao, Xiaoming Li, and Steve Uhlig. 2018b. Elastic Sketch: Adaptive and Fast Network-wide Measurements. In Proc. of ACM SIGCOMM. 561-575.","journal-title":"Adaptive and Fast Network-wide Measurements. In Proc. of ACM SIGCOMM."},{"key":"e_1_2_1_40_1","first-page":"103","article-title":"SF-sketch: A Fast, Accurate, and Memory Efficient Data Structure to Store Frequencies of Data Items","author":"Yang Tong","year":"2017","unstructured":"Tong Yang, Lingtong Liu, Yibo Yan, Muhammad Shahzad, Yulong Shen, Xiaoming Li, Bin Cui, and Gaogang Xie. 2017a. SF-sketch: A Fast, Accurate, and Memory Efficient Data Structure to Store Frequencies of Data Items. In Proc. of IEEE ICDE. 103-106.","journal-title":"Proc. of IEEE ICDE."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2019.2933868"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137652"},{"key":"e_1_2_1_43_1","first-page":"207","article-title":"CocoSketch: High-Performance Sketch-Based Measurement Over Arbitrary Partial Key Query","author":"Zhang Yinda","year":"2021","unstructured":"Yinda Zhang, Zaoxing Liu, Ruixin Wang, Tong Yang, Jizhou Li, Ruijie Miao, Peng Liu, Ruwen Zhang, and Junchen Jiang. 2021. CocoSketch: High-Performance Sketch-Based Measurement Over Arbitrary Partial Key Query. In Proc. of ACM SIGCOMM. 207-222.","journal-title":"Proc. of ACM SIGCOMM."},{"key":"e_1_2_1_44_1","first-page":"1","article-title":"Pontus: Finding waves in data streams","author":"Zhang Zhengxin","year":"2023","unstructured":"Zhengxin Zhang, Qing Li, Guanglin Duan, Dan Zhao, Jingyu Xiao, Guorui Xie, and Yong Jiang. 2023. Pontus: Finding waves in data streams. In Proc. of ACM SIGMOD. 1-26.","journal-title":"Proc. of ACM SIGMOD."},{"key":"e_1_2_1_45_1","first-page":"2285","article-title":"DHS","author":"Zhao Bohan","year":"2021","unstructured":"Bohan Zhao, Xiang Li, Boyu Tian, Zhiyu Mei, and Wenfei Wu. 2021. DHS: Adaptive Memory Layout Organization of Sketch Slots for Fast and Accurate Data Stream Processing. In Proc. of ACM SIGKDD. 2285-2293.","journal-title":"In Proc. of ACM SIGKDD."},{"key":"e_1_2_1_46_1","first-page":"1","article-title":"Double-Anonymous Sketch: Achieving Top-K-fairness for Finding Global Top-K Frequent Items","author":"Zhao Yikai","year":"2023","unstructured":"Yikai Zhao, Wenchen Han, Zheng Zhong, Yinda Zhang, Tong Yang, and Bin Cui. 2023. Double-Anonymous Sketch: Achieving Top-K-fairness for Finding Global Top-K Frequent Items. In Proc. of ACM SIGMOD, 1-26.","journal-title":"Proc. of ACM SIGMOD"},{"key":"e_1_2_1_47_1","first-page":"1","article-title":"One Memory Access Sketch","author":"Zhou Yang","year":"2017","unstructured":"Yang Zhou, Peng Liu, Hao Jin, Tong Yang, Shoujiang Dang, and Xiaoming Li. 2017. One Memory Access Sketch: A More Accurate and Faster Sketch for Per-Flow Measurement. In Proc. of IEEE GLOBECOM. 1-6.","journal-title":"In Proc. of IEEE GLOBECOM."},{"key":"e_1_2_1_48_1","first-page":"741","article-title":"Cold Filter","author":"Zhou Yang","year":"2018","unstructured":"Yang Zhou, Tong Yang, Jie Jiang, Bin Cui, Minlan Yu, Xiaoming Li, and Steve Uhlig. 2018. Cold Filter: A Meta-Framework for Faster and More Accurate Stream Processing. In Proc. of ACM SIGMOD. 741-756.","journal-title":"In Proc. of ACM SIGMOD."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3749182","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:39:38Z","timestamp":1781325578000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3749182"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,22]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,9,22]]}},"alternative-id":["10.1145\/3749182"],"URL":"https:\/\/doi.org\/10.1145\/3749182","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,22]]}}}