{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:11:07Z","timestamp":1785543067976,"version":"3.56.0"},"publisher-location":"New York, NY, USA","reference-count":47,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,10,21]],"date-time":"2024-10-21T00:00:00Z","timestamp":1729468800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/https:\/\/doi.org\/10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62102203, 62221003, 62132004, 62372123"],"award-info":[{"award-number":["62102203, 62221003, 62132004, 62372123"]}],"id":[{"id":"10.13039\/https:\/\/doi.org\/10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Basic Research Enhancement Program of China","award":["2021-JCJQ-JJ-0483"],"award-info":[{"award-number":["2021-JCJQ-JJ-0483"]}]},{"name":"the Major Key Project of Peng Cheng Laboratory","award":["PCL2023A06"],"award-info":[{"award-number":["PCL2023A06"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,10,21]]},"DOI":"10.1145\/3627673.3679882","type":"proceedings-article","created":{"date-parts":[[2024,10,20]],"date-time":"2024-10-20T19:34:21Z","timestamp":1729452861000},"page":"3653-3657","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Bubble Sketch: A High-performance and Memory-efficient Sketch for Finding Top-\n            <i>k<\/i>\n            Items in Data Streams"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-4123-2471","authenticated-orcid":false,"given":"Lu","family":"Cao","sequence":"first","affiliation":[{"name":"Harbin Institute of Technology, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5550-0692","authenticated-orcid":false,"given":"Qilong","family":"Shi","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-1341-3279","authenticated-orcid":false,"given":"Yuxi","family":"Liu","sequence":"additional","affiliation":[{"name":"Pengcheng Laboratory, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-7548-2882","authenticated-orcid":false,"given":"Hanyue","family":"Zheng","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6495-081X","authenticated-orcid":false,"given":"Yao","family":"Xin","sequence":"additional","affiliation":[{"name":"Guangzhou University, Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9234-0763","authenticated-orcid":false,"given":"Wenjun","family":"Li","sequence":"additional","affiliation":[{"name":"Pengcheng Laboratory, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2402-5854","authenticated-orcid":false,"given":"Tong","family":"Yang","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2713-0748","authenticated-orcid":false,"given":"Yangyang","family":"Wang","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0958-8547","authenticated-orcid":false,"given":"Yang","family":"Xu","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4783-876X","authenticated-orcid":false,"given":"Weizhe","family":"Zhang","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Harbin, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4847-4585","authenticated-orcid":false,"given":"Mingwei","family":"Xu","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,10,21]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Our GitHub. https:\/\/github.com\/wenjunpaper\/BubbleSketch."},{"key":"e_1_3_2_1_2_1","volume-title":"SALSA: Self-Adjusting Lean Streaming Analytics","author":"Basat Ran Ben","year":"2021","unstructured":"Ran Ben Basat, Gil Einziger, Michael Mitzenmacher, and Shay Vargaftik. 2021. SALSA: Self-Adjusting Lean Streaming Analytics. In IEEE ICDE."},{"key":"e_1_3_2_1_3_1","volume-title":"Heavy hitters in streams and sliding windows","author":"Ben-Basat Ran","unstructured":"Ran Ben-Basat, Gil Einziger, Roy Friedman, and Yaron Kassner. 2016. Heavy hitters in streams and sliding windows. In IEEE INFOCOM."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Ran Ben Basat Gil Einziger Roy Friedman Marcelo C Luizelli and ErezWaisbard. 2017. Constant time updates in hierarchical heavy hitters. In ACM SIGCOMM.","DOI":"10.1145\/3098822.3098832"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Moses Charikar Kevin Chen and Martin Farach-Colton. 2002. Finding frequent items in data streams. In ICALP.","DOI":"10.1007\/3-540-45465-9_59"},{"key":"e_1_3_2_1_6_1","volume-title":"Tracking long duration flows in network traffic","author":"Chen Aiyou","unstructured":"Aiyou Chen, Yu Jin, Jin Cao, and Li Erran Li. 2010. Tracking long duration flows in network traffic. In IEEE INFOCOM."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2016.2621159"},{"key":"e_1_3_2_1_8_1","volume-title":"Sketch techniques for approximate query processing. Foundations and Trends in Databases","author":"Cormode Graham","year":"2011","unstructured":"Graham Cormode. 2011. Sketch techniques for approximate query processing. Foundations and Trends in Databases. NOW publishers (2011), 15."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Graham Cormode Flip Korn Shanmugavelayutham Muthukrishnan and Divesh Srivastava. 2003. Finding hierarchical heavy hitters in data streams. In ACM VLDB.","DOI":"10.1016\/B978-012722442-8\/50048-3"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_3_2_1_11_1","unstructured":"Garofalakis M Cormode G. 2005. Sketching streams through the net: Distributed approximate query tracking. In ACM VLDB."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2019.2946417"},{"key":"e_1_3_2_1_13_1","unstructured":"Haipeng Dai Yuankun Zhong Alex X Liu Wei Wang and Meng Li. 2016. Noisy bloom filters for multi-set membership testing. In ACM SIGMETRICS."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3278028"},{"key":"e_1_3_2_1_15_1","unstructured":"Cooperative Association for Internet Data Analysis. 2016. The CAIDA Traces. http:\/\/www.caida.org\/data\/overview\/"},{"key":"e_1_3_2_1_16_1","volume-title":"Runhui Li, Lu Tang, Yi-Chao Chen, and Gong Zhang.","author":"Huang Qun","year":"2017","unstructured":"Qun Huang, Xin Jin, Patrick PC Lee, Runhui Li, Lu Tang, Yi-Chao Chen, and Gong Zhang. 2017. Sketchvisor: Robust network measurement for software packet processing. In ACM SIGCOMM."},{"key":"e_1_3_2_1_17_1","volume-title":"LD-sketch: A distributed sketching design for accurate and scalable anomaly detection in network data streams","author":"Huang Qun","unstructured":"Qun Huang and Patrick PC Lee. 2014. LD-sketch: A distributed sketching design for accurate and scalable anomaly detection in network data streams. In IEEE INFOCOM."},{"key":"e_1_3_2_1_18_1","volume-title":"Patrick PC Lee, and Yungang Bao","author":"Huang Qun","year":"2018","unstructured":"Qun Huang, Patrick PC Lee, and Yungang Bao. 2018. Sketchlearn: Relieving user burdens in approximate measurement with automated statistical inference. In ACM SIGCOMM."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Anukool Lakhina Mark Crovella and Christiphe Diot. 2004. Characterization of network-wide anomalies in traffic flows. In ACM SIGCOMM.","DOI":"10.1145\/1028788.1028813"},{"key":"e_1_3_2_1_20_1","unstructured":"Haoyu Li Qizhi Chen Yixin Zhang Tong Yang and Bin Cui. 2022. Stingy sketch: a sketch framework for accurate and fast frequency estimation. In ACM VLDB."},{"key":"e_1_3_2_1_21_1","volume-title":"Wavingsketch: An unbiased and generic sketch for finding top-k items in data streams. In ACM SIGKDD.","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 ACM SIGKDD."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3273709"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-022-00755-z"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2012.2192447"},{"key":"e_1_3_2_1_25_1","unstructured":"Weihe Li and Paul Patras. 2023. Tight-Sketch: A High-Performance Sketch for Heavy Item-Oriented Data Stream Mining with Limited Memory Size. In ACM CIKM."},{"key":"e_1_3_2_1_26_1","unstructured":"Yuliang Li Rui Miao Changhoon Kim and Minlan Yu. 2016. FlowRadar: A Better NetFlow for Data Centers. In USENIX NSDI."},{"key":"e_1_3_2_1_27_1","unstructured":"Gurmeet Singh Manku and Rajeev Motwani. 2002. Approximate frequency counts over data streams. In ACM VLDB."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2019.2918929"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166084"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Ahmed Metwally Divyakant Agrawal and Amr El Abbadi. 2005. Efficient computation of frequent and top-k elements in data streams. In ICDT.","DOI":"10.1007\/978-3-540-30570-5_27"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2007.896150"},{"key":"e_1_3_2_1_32_1","volume-title":"BitMatcher: Bit-level Counter Adjustment for Sketches","author":"Shi Qilong","unstructured":"Qilong Shi, Chengjun Jia, Wenjun Li, Zaoxing Liu, Tong Yang, Jianan Ji, Gaogang Xie, Weizhe Zhang, and Minlan Yu. 2024. BitMatcher: Bit-level Counter Adjustment for Sketches. In IEEE ICDE."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2022.3232098"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Anirudh Sivaraman Suvinay Subramanian Mohammad Alizadeh Sharad Chole Shang-Tse Chuang Anurag Agrawal Hari Balakrishnan Tom Edsall Sachin Katti and Nick McKeown. 2016. Programmable packet scheduling at line rate. In ACM SIGCOMM.","DOI":"10.1145\/2934872.2934899"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2020.3011798"},{"key":"e_1_3_2_1_36_1","volume-title":"SpreadSketch: Toward invertible and network-wide detection of superspreaders","author":"Tang Lu","unstructured":"Lu Tang, Qun Huang, and Patrick PC Lee. 2020. SpreadSketch: Toward invertible and network-wide detection of superspreaders. In IEEE INFOCOM."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Daniel Ting. 2018. Data sketches for disaggregated subset sum and frequent item estimation. In ACM SIGMOD.","DOI":"10.1145\/3183713.3183759"},{"key":"e_1_3_2_1_38_1","volume-title":"She: A generic framework for data stream mining over sliding windows. In ICPP.","author":"Wu Yuhan","year":"2022","unstructured":"Yuhan Wu, Zhuochen Fan, Qilong Shi, Yixin Zhang, Tong Yang, Cheng Chen, Zheng Zhong, Junnan Li, Ariel Shtul, and Yaofeng Tu. 2022. She: A generic framework for data stream mining over sliding windows. In ICPP."},{"key":"e_1_3_2_1_39_1","volume-title":"Hash adaptive bloom filter","author":"Xie Rongbiao","unstructured":"Rongbiao Xie, Meng Li, Zheyu Miao, Rong Gu, He Huang, Haipeng Dai, and Guihai Chen. 2021. Hash adaptive bloom filter. In IEEE ICDE."},{"key":"e_1_3_2_1_40_1","volume-title":"SketchINT: Empowering INT with TowerSketch for per-flow per-switch measurement","author":"Yang Kaicheng","year":"2023","unstructured":"Kaicheng Yang, Sheng Long, Qilong Shi, Yuanpeng Li, Zirui Liu, YuhanWu, Tong Yang, and Zhengyi Jia. 2023. SketchINT: Empowering INT with TowerSketch for per-flow per-switch measurement. IEEE Transactions on Parallel and Distributed Systems (2023)."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2019.2923772"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Tong Yang Jie Jiang Peng Liu Qun Huang Junzhi Gong Yang Zhou Rui Miao Xiaoming Li and Steve Uhlig. 2018. Elastic sketch: Adaptive and fast networkwide measurements. In ACM SIGCOMM.","DOI":"10.1145\/3230543.3230544"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2019.2933868"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Tong Yang Yang Zhou Hao Jin Shigang Chen and Xiaoming Li. 2017. Pyramid sketch: A sketch framework for frequency estimation of data streams. In ACM VLDB.","DOI":"10.14778\/3137628.3137652"},{"key":"e_1_3_2_1_45_1","unstructured":"Minlan Yu Lavanya Jose and Rui Miao. 2013. Software Defined Traffic Measurement with OpenSketch. In USENIX NSDI."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467353"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"crossref","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 ACM SIGMOD.","DOI":"10.1145\/3588933"}],"event":{"name":"CIKM '24: The 33rd ACM International Conference on Information and Knowledge Management","location":"Boise ID USA","acronym":"CIKM '24","sponsor":["SIGIR ACM Special Interest Group on Information Retrieval"]},"container-title":["Proceedings of the 33rd ACM International Conference on Information and Knowledge Management"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3627673.3679882","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3627673.3679882","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:58:08Z","timestamp":1750294688000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3627673.3679882"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,21]]},"references-count":47,"alternative-id":["10.1145\/3627673.3679882","10.1145\/3627673"],"URL":"https:\/\/doi.org\/10.1145\/3627673.3679882","relation":{},"subject":[],"published":{"date-parts":[[2024,10,21]]},"assertion":[{"value":"2024-10-21","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}