{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T16:23:10Z","timestamp":1783009390945,"version":"3.54.5"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:p>Private collection of statistics from a large distributed population is an important problem, and has led to large scale deployments from several leading technology companies. The dominant approach requires each user to randomly perturb their input, leading to guarantees in the local differential privacy model. In this paper, we place the various approaches that have been suggested into a common framework, and perform an extensive series of experiments to understand the tradeoffs between different implementation choices. Our conclusion is that for the core problems of frequency estimation and heavy hitter identification, careful choice of algorithms can lead to very effective solutions that scale to millions of users.<\/jats:p>","DOI":"10.14778\/3476249.3476261","type":"journal-article","created":{"date-parts":[[2021,10,27]],"date-time":"2021-10-27T16:46:23Z","timestamp":1635353183000},"page":"2046-2058","source":"Crossref","is-referenced-by-count":56,"title":["Frequency estimation under local differential privacy"],"prefix":"10.14778","volume":"14","author":[{"given":"Graham","family":"Cormode","sequence":"first","affiliation":[{"name":"University of Warwick"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Samuel","family":"Maddock","sequence":"additional","affiliation":[{"name":"University of Warwick"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carsten","family":"Maple","sequence":"additional","affiliation":[{"name":"University of Warwick"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,10,27]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Sample Optimal, Linear Time Locally Private Discrete Distribution Estimation. CoRR abs\/1802.04705","author":"Acharya Jayadev","year":"2018","unstructured":"Jayadev Acharya , Ziteng Sun , and Huanyu Zhang . 2018. Communication Efficient , Sample Optimal, Linear Time Locally Private Discrete Distribution Estimation. CoRR abs\/1802.04705 ( 2018 ). arXiv:1802.04705 http:\/\/arxiv.org\/abs\/1802.04705 Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. 2018. Communication Efficient, Sample Optimal, Linear Time Locally Private Discrete Distribution Estimation. CoRR abs\/1802.04705 (2018). arXiv:1802.04705 http:\/\/arxiv.org\/abs\/1802.04705"},{"key":"e_1_2_1_2_1","volume-title":"The 22nd International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research)","volume":"89","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 (Proceedings of Machine Learning Research) , Vol. 89 . PMLR, 1120--1129. http:\/\/proceedings.mlr.press\/v89\/acharya19a.html 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 (Proceedings of Machine Learning Research), Vol. 89. PMLR, 1120--1129. http:\/\/proceedings.mlr.press\/v89\/acharya19a.html"},{"key":"e_1_2_1_3_1","unstructured":"Apple. 2017. Apple differential privacy technical overview. https:\/\/www.apple.com\/privacy\/docs\/Differential_Privacy_Overview.pdf last accessed 19\/07\/21.  Apple. 2017. Apple differential privacy technical overview. https:\/\/www.apple.com\/privacy\/docs\/Differential_Privacy_Overview.pdf last accessed 19\/07\/21."},{"key":"e_1_2_1_4_1","article-title":"Practical Locally Private Heavy Hitters","volume":"21","author":"Bassily Raef","year":"2020","unstructured":"Raef Bassily , Kobbi Nissim , Uri Stemmer , and Abhradeep Thakurta . 2020 . Practical Locally Private Heavy Hitters . J. Mach. Learn. Res. 21 (2020), 16:1--16:42. http:\/\/jmlr.org\/papers\/v21\/18-786.html Raef Bassily, Kobbi Nissim, Uri Stemmer, and Abhradeep Thakurta. 2020. Practical Locally Private Heavy Hitters. J. Mach. Learn. Res. 21 (2020), 16:1--16:42. http:\/\/jmlr.org\/papers\/v21\/18-786.html","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746632"},{"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.5555\/646255.684566"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3197390"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339496"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Graham Cormode and Ke Yi. 2020. Small Summaries for Big Data. CUP. http:\/\/cormode.org\/ssbd  Graham Cormode and Ke Yi. 2020. Small Summaries for Big Data. CUP. http:\/\/cormode.org\/ssbd","DOI":"10.1017\/9781108769938"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660348"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1515\/popets-2016-0015"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00079"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/3241189.3241247"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2019.2927695"},{"key":"e_1_2_1_17_1","volume-title":"Locally Differentially Private Frequency Estimation with Consistency. In 27th Annual Network and Distributed System Security Symposium, NDSS 2020","author":"Wang Tianhao","year":"2020","unstructured":"Tianhao Wang , Milan Lopuha\u00e4-Zwakenberg , Zitao Li , Boris Skoric , and Ninghui Li . 2020 . Locally Differentially Private Frequency Estimation with Consistency. In 27th Annual Network and Distributed System Security Symposium, NDSS 2020 , San Diego, California, USA, February 23--26 , 2020. The Internet Society. https:\/\/www.ndss-symposium.org\/ndss-paper\/locally-differentially-private-frequency-estimation-with-consistency\/ Tianhao Wang, Milan Lopuha\u00e4-Zwakenberg, Zitao Li, Boris Skoric, and Ninghui Li. 2020. Locally Differentially Private Frequency Estimation with Consistency. In 27th Annual Network and Distributed System Security Symposium, NDSS 2020, San Diego, California, USA, February 23--26, 2020. The Internet Society. https:\/\/www.ndss-symposium.org\/ndss-paper\/locally-differentially-private-frequency-estimation-with-consistency\/"},{"key":"e_1_2_1_18_1","volume-title":"A Comprehensive Survey on Local Differential Privacy Toward Data Statistics and Analysis in Crowdsensing. CoRR abs\/2010.05253","author":"Wang Teng","year":"2020","unstructured":"Teng Wang , Xuefeng Zhang , Jingyu Feng , and Xinyu Yang . 2020. A Comprehensive Survey on Local Differential Privacy Toward Data Statistics and Analysis in Crowdsensing. CoRR abs\/2010.05253 ( 2020 ). arXiv:2010.05253 https:\/\/arxiv.org\/abs\/2010.05253 Teng Wang, Xuefeng Zhang, Jingyu Feng, and Xinyu Yang. 2020. A Comprehensive Survey on Local Differential Privacy Toward Data Statistics and Analysis in Crowdsensing. CoRR abs\/2010.05253 (2020). arXiv:2010.05253 https:\/\/arxiv.org\/abs\/2010.05253"},{"key":"e_1_2_1_19_1","volume-title":"Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application. CoRR abs\/1309.1541","author":"Wang Weiran","year":"2013","unstructured":"Weiran Wang and Miguel \u00c1. Carreira-Perpi\u00f1\u00e1n . 2013. Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application. CoRR abs\/1309.1541 ( 2013 ). arXiv:1309.1541 http:\/\/arxiv.org\/abs\/1309.1541 Weiran Wang and Miguel \u00c1. Carreira-Perpi\u00f1\u00e1n. 2013. Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application. CoRR abs\/1309.1541 (2013). arXiv:1309.1541 http:\/\/arxiv.org\/abs\/1309.1541"},{"key":"e_1_2_1_20_1","volume-title":"Local Differential Privacy and Its Applications: A Comprehensive Survey. CoRR abs\/2008.03686","author":"Yang Mengmeng","year":"2020","unstructured":"Mengmeng Yang , Lingjuan Lyu , Jun Zhao , Tianqing Zhu , and Kwok-Yan Lam . 2020. Local Differential Privacy and Its Applications: A Comprehensive Survey. CoRR abs\/2008.03686 ( 2020 ). arXiv:2008.03686 https:\/\/arxiv.org\/abs\/2008.03686 Mengmeng Yang, Lingjuan Lyu, Jun Zhao, Tianqing Zhu, and Kwok-Yan Lam. 2020. Local Differential Privacy and Its Applications: A Comprehensive Survey. CoRR abs\/2008.03686 (2020). arXiv:2008.03686 https:\/\/arxiv.org\/abs\/2008.03686"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3476249.3476261","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:57:22Z","timestamp":1672221442000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3476249.3476261"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7]]},"references-count":20,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["10.14778\/3476249.3476261"],"URL":"https:\/\/doi.org\/10.14778\/3476249.3476261","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,7]]}}}