{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T23:23:01Z","timestamp":1791501781613,"version":"4.3.4"},"reference-count":65,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"The Major Programs of the National Social Science Foundation of China under Grant","award":["22&ZD147"],"award-info":[{"award-number":["22&ZD147"]}]},{"name":"The National Key Research and Development Program of China under Grant","award":["Grant 2021YFB3100300"],"award-info":[{"award-number":["Grant 2021YFB3100300"]}]},{"name":"The National Science Foundation under Grants","award":["CNS-2308730, CNS-2302689, CNS-2319277, CMMI-2326341"],"award-info":[{"award-number":["CNS-2308730, CNS-2302689, CNS-2319277, CMMI-2326341"]}]},{"name":"The National Natural Science Foundation of China under Grant","award":["U20A20178, 62072395"],"award-info":[{"award-number":["U20A20178, 62072395"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>Top-k frequent items detection is a fundamental task in data stream mining. Many promising solutions are proposed to improve memory efficiency while still maintaining high accuracy for detecting the Top-k items. Despite the memory efficiency concern, the users could suffer from privacy loss if participating in the task without proper protection, since their contributed local data streams may continually leak sensitive individual information. However, most existing works solely focus on addressing either the memory-efficiency problem or the privacy concerns but seldom jointly, which cannot achieve a satisfactory tradeoff between memory efficiency, privacy protection, and detection accuracy.<\/jats:p>\n                  <jats:p>In this paper, we present a novel framework HG-LDP to achieve accurate Top-k item detection at bounded memory expense, while providing rigorous local differential privacy (LDP) protection. Specifically, we identify two key challenges naturally arising in the task, which reveal that directly applying existing LDP techniques will lead to an inferior \"accuracy-privacy-memory efficiency\" tradeoff. Therefore, we instantiate three advanced schemes under the framework by designing novel LDP randomization methods, which address the hurdles caused by the large size of the item domain and by the limited space of the memory. We conduct comprehensive experiments on both synthetic and real-world datasets to show that the proposed advanced schemes achieve a superior \"accuracy-privacy-memory efficiency\" tradeoff, saving 2300\u00d7 memory over baseline methods when the item domain size is 41,270. Our code is anonymously open-sourced via the link.<\/jats:p>","DOI":"10.1145\/3639285","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-27","source":"Crossref","is-referenced-by-count":15,"title":["Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3722-4783","authenticated-orcid":false,"given":"Xiaochen","family":"Li","sequence":"first","affiliation":[{"name":"The State Key Laboratory of Blockchain and Data Security, Zhejiang university, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1466-7418","authenticated-orcid":false,"given":"Weiran","family":"Liu","sequence":"additional","affiliation":[{"name":"Alibaba Group, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4110-2068","authenticated-orcid":false,"given":"Jian","family":"Lou","sequence":"additional","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4095-4506","authenticated-orcid":false,"given":"Yuan","family":"Hong","sequence":"additional","affiliation":[{"name":"University of Connecticut, Mansfield, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-8102-6568","authenticated-orcid":false,"given":"Lei","family":"Zhang","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7872-6969","authenticated-orcid":false,"given":"Zhan","family":"Qin","sequence":"additional","affiliation":[{"name":"The State Key Laboratory of Blockchain and Data Security, Zhejiang University, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3441-6277","authenticated-orcid":false,"given":"Kui","family":"Ren","sequence":"additional","affiliation":[{"name":"The State Key Laboratory of Blockchain and Data Security, Zhejiang University, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"1999. Frequent Itemset Mining Dataset Repository retail. http:\/\/fimi.uantwerpen.be\/data\/."},{"key":"e_1_2_2_2_1","unstructured":"2004. Frequent Itemset Mining Dataset Repository webdocs. http:\/\/fimi.uantwerpen.be\/data\/webdocs.dat.gz."},{"key":"e_1_2_2_3_1","unstructured":"2015. Frequent Itemset Mining Dataset Repository kosarak. http:\/\/fimi.uantwerpen.be\/data\/."},{"key":"e_1_2_2_4_1","unstructured":"2023. How Many Videos Are on YouTube: Exploring the Vast Digital Landscape. https:\/\/www.techpluto.com\/how-many-videos-are-on-youtube\/."},{"key":"e_1_2_2_5_1","volume-title":"International Conference on Machine Learning. PMLR, 51--60","author":"Acharya Jayadev","year":"2019","unstructured":"Jayadev Acharya and Ziteng Sun. 2019. Communication complexity in locally private distribution estimation and heavy hitters. In International Conference on Machine Learning. PMLR, 51--60."},{"key":"e_1_2_2_6_1","volume-title":"The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 1120--1129","author":"Acharya Jayadev","year":"2019","unstructured":"Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. 2019. Hadamard response: Estimating distributions privately, efficiently, and with little communication. In The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 1120--1129."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/060674417"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476277"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2021.3132385"},{"key":"e_1_2_2_11_1","volume-title":"Practical Locally Private Heavy Hitters. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017","author":"Bassily Raef","year":"2017","unstructured":"Raef Bassily, Kobbi Nissim, Uri Stemmer, and Abhradeep Guha Thakurta. 2017. Practical Locally Private Heavy Hitters. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4--9, 2017, Long Beach, CA, USA, Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (Eds.). 2288--2296."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2016.7524364"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897558"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--642--14162--1_34"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1541880.1541882"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2749451"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134102"},{"key":"e_1_2_2_18_1","volume-title":"Fourth IEEE International Conference on Data Mining (ICDM'04)","author":"Chi Yun","year":"2004","unstructured":"Yun Chi, Haixun Wang, Philip S Yu, and Richard R Muntz. 2004. Moment: Maintaining closed frequent itemsets over a stream sliding window. In Fourth IEEE International Conference on Data Mining (ICDM'04). IEEE, 59--66."},{"key":"e_1_2_2_19_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_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454225"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012722442-8\/50048-3"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476261"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061325"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1325851.1325875"},{"key":"e_1_2_2_26_1","volume-title":"Collecting telemetry data privately. Advances in Neural Information Processing Systems 30","author":"Ding Bolin","year":"2017","unstructured":"Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. 2017. Collecting telemetry data privately. Advances in Neural Information Processing Systems 30 (2017)."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/11787006_1"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806787"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806787"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000042"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660348"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660348"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773174"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCPS48487.2020.00008"},{"key":"e_1_2_2_35_1","volume-title":"DPI: Ensuring Strict Differential Privacy for Infinite Data Streaming. arXiv preprint arXiv:2312.04738","author":"Feng Shuya","year":"2023","unstructured":"Shuya Feng, Meisam Mohammady, Han Wang, Xiaochen Li, Zhan Qin, and Yuan Hong. 2023. DPI: Ensuring Strict Differential Privacy for Infinite Data Streaming. arXiv preprint arXiv:2312.04738 (2023)."},{"key":"e_1_2_2_36_1","volume-title":"International Conference on Machine Learning, ICML 2022","volume":"7582","author":"Gillenwater Jennifer","year":"2022","unstructured":"Jennifer Gillenwater, Matthew Joseph, Andres Mu\u00f1oz Medina, and M\u00f3nica Ribero Diaz. 2022. A Joint Exponential Mechanism For Differentially Private Top-k. In International Conference on Machine Learning, ICML 2022, 17--23 July 2022, Baltimore, Maryland, USA (Proceedings of Machine Learning Research, Vol. 162), Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesv\u00e1ri, Gang Niu, and Sivan Sabato (Eds.). PMLR, 7570--7582."},{"key":"e_1_2_2_37_1","volume-title":"Wired","author":"Greenberg Andy","year":"2016","unstructured":"Andy Greenberg. 2016. Apple's \"differential privacy'is about collecting your data-but not your data. Wired, June 13 (2016)."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375670"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0171-0"},{"key":"e_1_2_2_40_1","volume-title":"Local differential privacy for evolving data. Advances in Neural Information Processing Systems 31","author":"Joseph Matthew","year":"2018","unstructured":"Matthew Joseph, Aaron Roth, Jonathan Ullman, and Bo Waggoner. 2018. Local differential privacy for evolving data. Advances in Neural Information Processing Systems 31 (2018)."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.27"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732989"},{"key":"e_1_2_2_43_1","volume-title":"et al","author":"Krempl Georg","year":"2014","unstructured":"Georg Krempl, Dariusz Brzezi'ski, Eyke H\u00fcllermeier, Mark Last, Vincent Lemaire, Tino Noack, Ammar Shaker, Sonja Sievi, Myra Spiliopoulou, et al . 2014. Open challenges for data stream mining research. ACM SIGKDD explorations newsletter 16, 1 (2014), 1--10."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3523210.3523220"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403208"},{"key":"e_1_2_2_46_1","volume-title":"Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory (full version). arXiv preprint arXiv:2311.16062","author":"Li Xiaochen","year":"2023","unstructured":"Xiaochen Li, Weiran Liu, Jian Lou, Yuan Hong, Lei Zhang, Zhan Qin, and Kui Ren. 2023. Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory (full version). arXiv preprint arXiv:2311.16062 (2023)."},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1735886.1735894"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-155860869-6\/50038-X"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--540--30570--5_27"},{"key":"e_1_2_2_50_1","volume-title":"Hassan Jameel Asghar, and Dali Kaafar","author":"Perrier Victor","year":"2018","unstructured":"Victor Perrier, Hassan Jameel Asghar, and Dali Kaafar. 2018. Private continual release of real-valued data streams. arXiv preprint arXiv:1811.03197 (2018)."},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978409"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526190"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882948"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031524"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1080\/10196780500208632"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2017.02.004"},{"key":"e_1_2_2_57_1","volume-title":"USENIX Security Symposium. 729--745","author":"Wang Tianhao","year":"2017","unstructured":"Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha. 2017. Locally differentially private protocols for frequency estimation. In USENIX Security Symposium. 729--745."},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460120.3484750"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.00035"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2019.2927695"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1965.10480775"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219978"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559820"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488519"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183726"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639285","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639285","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:16:08Z","timestamp":1755789368000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639285"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":65,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639285"],"URL":"https:\/\/doi.org\/10.1145\/3639285","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}