{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T20:52:20Z","timestamp":1725655940985},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,6]]},"abstract":"\n We study the fundamental problem of frequency estimation under both privacy and communication constraints, where the data is distributed among\n k<\/jats:italic>\n parties. We consider two application scenarios: (1) one-shot, where the data is static and the aggregator conducts a one-time computation; and (2) streaming, where each party receives a stream of items over time and the aggregator continuously monitors the frequencies. We adopt the model of multiparty differential privacy (MDP), which is more general than local differential privacy (LDP) and (centralized) differential privacy. Our protocols achieve optimality (up to logarithmic factors) permissible by the more stringent of the two constraints. In particular, when specialized to the \u03b5-LDP model, our protocol achieves an error of \u221a\n k<\/jats:italic>\n \/(\u03b5\n \u0398(\u03b5)<\/jats:sup>\n \u2212 1) using\n O<\/jats:italic>\n (\n k<\/jats:italic>\n max{\u03b5, log 1\/\u03b5}) bits of communication and\n O<\/jats:italic>\n (\n k<\/jats:italic>\n log\n u<\/jats:italic>\n ) bits of public randomness, where\n u<\/jats:italic>\n is the size of the domain.\n <\/jats:p>","DOI":"10.14778\/3547305.3547312","type":"journal-article","created":{"date-parts":[[2022,9,7]],"date-time":"2022-09-07T16:09:53Z","timestamp":1662566993000},"page":"2058-2070","source":"Crossref","is-referenced-by-count":5,"title":["Frequency estimation under multiparty differential privacy"],"prefix":"10.14778","volume":"15","author":[{"given":"Ziyue","family":"Huang","sequence":"first","affiliation":[{"name":"Hong Kong University of Science and Technology"}]},{"given":"Yuan","family":"Qiu","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology"}]},{"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology"}]},{"given":"Graham","family":"Cormode","sequence":"additional","affiliation":[{"name":"University of Warwick"}]}],"member":"320","published-online":{"date-parts":[[2022,9,7]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"51","volume-title":"International Conference on Machine Learning","author":"Acharya J.","year":"2019","unstructured":"J. Acharya and Z. Sun . Communication complexity in locally private distribution estimation and heavy hitters . In International Conference on Machine Learning , pages 51 -- 60 . PMLR, 2019 . J. Acharya and Z. Sun. Communication complexity in locally private distribution estimation and heavy hitters. In International Conference on Machine Learning, pages 51--60. PMLR, 2019."},{"key":"e_1_2_1_2_1","first-page":"1120","volume-title":"The 22nd International Conference on Artificial Intelligence and Statistics","author":"Acharya J.","year":"2019","unstructured":"J. Acharya , Z. Sun , and H. Zhang . Hadamard response: Estimating distributions privately, efficiently, and with little communication . In The 22nd International Conference on Artificial Intelligence and Statistics , pages 1120 -- 1129 , 2019 . J. Acharya, Z. Sun, and H. Zhang. Hadamard response: Estimating distributions privately, efficiently, and with little communication. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1120--1129, 2019."},{"key":"e_1_2_1_3_1","first-page":"7564","volume-title":"Advances in Neural Information Processing Systems","author":"Agarwal N.","year":"2018","unstructured":"N. Agarwal , A. T. Suresh , F. X. X. Yu , S. Kumar , and B. McMahan . cpsgd: Communication-efficient and differentially-private distributed sgd . In Advances in Neural Information Processing Systems , pages 7564 -- 7575 , 2018 . N. Agarwal, A. T. Suresh, F. X. X. Yu, S. Kumar, and B. McMahan. cpsgd: Communication-efficient and differentially-private distributed sgd. In Advances in Neural Information Processing Systems, pages 7564--7575, 2018."},{"key":"e_1_2_1_4_1","volume-title":"Apple differential privacy technical overview. https:\/\/www.apple.com\/privacy\/docs\/Differential_Privacy_Overview.pdf","year":"2017","unstructured":"Apple. Apple differential privacy technical overview. https:\/\/www.apple.com\/privacy\/docs\/Differential_Privacy_Overview.pdf , 2017 . [Last accessed on 5-June-2022]. Apple. Apple differential privacy technical overview. https:\/\/www.apple.com\/privacy\/docs\/Differential_Privacy_Overview.pdf, 2017. [Last accessed on 5-June-2022]."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26951-7_22"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265569"},{"key":"e_1_2_1_7_1","first-page":"2285","volume-title":"Neural Information Processing Systems","author":"Bassily R.","year":"2017","unstructured":"R. Bassily , K. Nissim , U. Stemmer , and A. Thakurta . Practical locally private heavy hitters . In Neural Information Processing Systems , pages 2285 -- 2293 , 2017 . R. Bassily, K. Nissim, U. Stemmer, and A. Thakurta. Practical locally private heavy hitters. In Neural Information Processing Systems, pages 2285--2293, 2017."},{"key":"e_1_2_1_8_1","first-page":"16","article-title":"Practical locally private heavy hitters","volume":"21","author":"Bassily R.","year":"2020","unstructured":"R. Bassily , K. Nissim , U. Stemmer , and A. Thakurta . Practical locally private heavy hitters . J. Mach. Learn. Res. , 21 : 16 :1--16:42, 2020 . R. Bassily, K. Nissim, U. Stemmer, and A. Thakurta. Practical locally private heavy hitters. J. Mach. Learn. Res., 21:16:1--16:42, 2020.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746632"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065184"},{"key":"e_1_2_1_11_1","first-page":"149","article-title":"Data stream algorithms","volume":"49","author":"Chakrabarti A.","year":"2015","unstructured":"A. Chakrabarti . Data stream algorithms . Computer Science , 49 : 149 , 2015 . A. Chakrabarti. Data stream algorithms. Computer Science, 49:149, 2015.","journal-title":"Computer Science"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_25"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31680-7_8"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043621.2043626"},{"key":"e_1_2_1_15_1","volume-title":"Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3):1--24","author":"Chan T.-H. H.","year":"2011","unstructured":"T.-H. H. Chan , E. Shi , and D. Song . Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3):1--24 , 2011 . T.-H. H. Chan, E. Shi, and D. Song. Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3):1--24, 2011."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/646255.684566"},{"key":"e_1_2_1_17_1","volume-title":"Advances in Neural Information Processing Systems","author":"Chen W.-N.","year":"2020","unstructured":"W.-N. Chen , P. Kairouz , and A. \u00d6zg\u00fcr . Breaking the communication-privacy-accuracy trilemma . In Advances in Neural Information Processing Systems , 2020 . W.-N. Chen, P. Kairouz, and A. \u00d6zg\u00fcr. Breaking the communication-privacy-accuracy trilemma. In Advances in Neural Information Processing Systems, 2020."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0172-z"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3197390"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339496"},{"key":"e_1_2_1_21_1","volume-title":"Frequency estimation under local differential privacy [experiments, analysis and benchmarks]. arXiv preprint arXiv:2103.16640","author":"Cormode G.","year":"2021","unstructured":"G. Cormode , S. Maddock , and C. Maple . Frequency estimation under local differential privacy [experiments, analysis and benchmarks]. arXiv preprint arXiv:2103.16640 , 2021 . G. Cormode, S. Maddock, and C. Maple. Frequency estimation under local differential privacy [experiments, analysis and benchmarks]. arXiv preprint arXiv:2103.16640, 2021."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"issue":"21","key":"e_1_2_1_23_1","first-page":"03","article-title":"Algorithms for distributed functional monitoring","volume":"7","author":"Cormode G.","year":"2011","unstructured":"G. Cormode , S. Muthukrishnan , and K. Yi . Algorithms for distributed functional monitoring . ACM Transactions on Algorithms , 7 : 21 , 03 2011 . G. Cormode, S. Muthukrishnan, and K. Yi. Algorithms for distributed functional monitoring. ACM Transactions on Algorithms, 7:21, 03 2011.","journal-title":"ACM Transactions on Algorithms"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2160158.2160163"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274608"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108769938"},{"key":"e_1_2_1_27_1","first-page":"3571","volume-title":"Advances in Neural Information Processing Systems","author":"Ding B.","year":"2017","unstructured":"B. Ding , J. Kulkarni , and S. Yekhanin . Collecting telemetry data privately . In Advances in Neural Information Processing Systems , pages 3571 -- 3580 , 2017 . B. Ding, J. Kulkarni, and S. Yekhanin. Collecting telemetry data privately. In Advances in Neural Information Processing Systems, pages 3571--3580, 2017."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806787"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000042"},{"key":"e_1_2_1_30_1","first-page":"2468","volume-title":"ACM-SIAM Symposium on Discrete Algorithms","author":"Feldman V.","year":"2019","unstructured":"\u00da. Erlingsson, V. Feldman , I. Mironov , A. Raghunathan , K. Talwar , and A. Thakurta . Amplification by shuffling: From local to central differential privacy via anonymity . In ACM-SIAM Symposium on Discrete Algorithms , pages 2468 -- 2479 , 2019 . \u00da. Erlingsson, V. Feldman, I. Mironov, A. Raghunathan, K. Talwar, and A. Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity. In ACM-SIAM Symposium on Discrete Algorithms, pages 2468--2479, 2019."},{"key":"e_1_2_1_31_1","first-page":"1054","volume-title":"ACM SIGSAC Conference on Computer and Communications Security","author":"Pihur V.","year":"2014","unstructured":"\u00da. Erlingsson, V. Pihur , and A. Korolova . RAPPOR: randomized aggregatable privacy-preserving ordinal response . In ACM SIGSAC Conference on Computer and Communications Security , pages 1054 -- 1067 . ACM, 2014 . \u00da. Erlingsson, V. Pihur, and A. Korolova. RAPPOR: randomized aggregatable privacy-preserving ordinal response. In ACM SIGSAC Conference on Computer and Communications Security, pages 1054--1067. ACM, 2014."},{"key":"e_1_2_1_32_1","volume-title":"International Conference on Machine Learning","volume":"139","author":"Feldman V.","year":"2021","unstructured":"V. Feldman and K. Talwar . Lossless compression of efficient private local randomizers . In International Conference on Machine Learning , volume 139 of Proceedings of Machine Learning Research, pages 3208--3219 , 18-24 Jul 2021 . V. Feldman and K. Talwar. Lossless compression of efficient private local randomizers. In International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 3208--3219, 18-24 Jul 2021."},{"key":"e_1_2_1_33_1","volume-title":"On the power of multiple anonymous messages. arXiv preprint arXiv:1908.11358","author":"Ghazi B.","year":"2019","unstructured":"B. Ghazi , N. Golowich , R. Kumar , R. Pagh , and A. Velingker . On the power of multiple anonymous messages. arXiv preprint arXiv:1908.11358 , 2019 . B. Ghazi, N. Golowich, R. Kumar, R. Pagh, and A. Velingker. On the power of multiple anonymous messages. arXiv preprint arXiv:1908.11358, 2019."},{"key":"e_1_2_1_34_1","first-page":"3505","volume-title":"International Conference on Machine Learning","author":"Ghazi B.","year":"2020","unstructured":"B. Ghazi , R. Kumar , P. Manurangsi , and R. Pagh . Private counting from anonymous messages: Near-optimal accuracy with vanishing communication overhead . In International Conference on Machine Learning , pages 3505 -- 3514 . PMLR, 2020 . B. Ghazi, R. Kumar, P. Manurangsi, and R. Pagh. Private counting from anonymous messages: Near-optimal accuracy with vanishing communication overhead. In International Conference on Machine Learning, pages 3505--3514. PMLR, 2020."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/09076828X"},{"key":"e_1_2_1_36_1","volume-title":"Frequency estimation under multiparty differential privacy: One-shot and streaming. arXiv preprint arXiv:2104.01808","author":"Huang Z.","year":"2021","unstructured":"Z. Huang , Y. Qiu , K. Yi , and G. Cormode . Frequency estimation under multiparty differential privacy: One-shot and streaming. arXiv preprint arXiv:2104.01808 , 2021 . Z. Huang, Y. Qiu, K. Yi, and G. Cormode. Frequency estimation under multiparty differential privacy: One-shot and streaming. arXiv preprint arXiv:2104.01808, 2021."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1093604"},{"key":"e_1_2_1_38_1","volume-title":"Advances and open problems in federated learning. arXiv preprint arXiv:1912.04977","author":"Kairouz P.","year":"2019","unstructured":"P. Kairouz and Advances and open problems in federated learning. arXiv preprint arXiv:1912.04977 , 2019 . P. Kairouz and et al. Advances and open problems in federated learning. arXiv preprint arXiv:1912.04977, 2019."},{"key":"e_1_2_1_39_1","volume-title":"Extremal mechanisms for local differential privacy. Advances in neural information processing systems, 27:2879--2887","author":"Kairouz P.","year":"2014","unstructured":"P. Kairouz , S. Oh , and P. Viswanath . Extremal mechanisms for local differential privacy. Advances in neural information processing systems, 27:2879--2887 , 2014 . P. Kairouz, S. Oh, and P. Viswanath. Extremal mechanisms for local differential privacy. Advances in neural information processing systems, 27:2879--2887, 2014."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497436"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.14"},{"key":"e_1_2_1_42_1","volume-title":"Finding repeated elements. Science of computer programming, 2(2):143--152","author":"Misra J.","year":"1982","unstructured":"J. Misra and D. Gries . Finding repeated elements. Science of computer programming, 2(2):143--152 , 1982 . J. Misra and D. Gries. Finding repeated elements. Science of computer programming, 2(2):143--152, 1982."},{"key":"e_1_2_1_43_1","volume-title":"Collecting and analyzing data from smart device users with local differential privacy. CoRR, abs\/1606.05053","author":"Nguy\u011bn T. T.","year":"2016","unstructured":"T. T. Nguy\u011bn , X. Xiao , Y. Yang , S. C. Hui , H. Shin , and J. Shin . Collecting and analyzing data from smart device users with local differential privacy. CoRR, abs\/1606.05053 , 2016 . T. T. Nguy\u011bn, X. Xiao, Y. Yang, S. C. Hui, H. Shin, and J. Shin. Collecting and analyzing data from smart device users with local differential privacy. CoRR, abs\/1606.05053, 2016."},{"key":"e_1_2_1_44_1","first-page":"1876","volume-title":"Advances in Neural Information Processing Systems","author":"Pathak M.","year":"2010","unstructured":"M. Pathak , S. Rane , and B. Raj . Multiparty differential privacy via aggregation of locally trained classifiers . In Advances in Neural Information Processing Systems , pages 1876 -- 1884 , 2010 . M. Pathak, S. Rane, and B. Raj. Multiparty differential privacy via aggregation of locally trained classifiers. In Advances in Neural Information Processing Systems, pages 1876--1884, 2010."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3146549"},{"key":"e_1_2_1_46_1","first-page":"6363","volume-title":"International Conference on Machine Learning","author":"Upadhyay J.","year":"2019","unstructured":"J. Upadhyay . Sublinear space private algorithms under the sliding window model . In International Conference on Machine Learning , pages 6363 -- 6372 . PMLR, 2019 . J. Upadhyay. Sublinear space private algorithms under the sliding window model. In International Conference on Machine Learning, pages 6363--6372. PMLR, 2019."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57048-8_7"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465312"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00079"},{"key":"e_1_2_1_50_1","first-page":"729","volume-title":"26th {USENIX} Security Symposium ({USENIX} Security 17)","author":"Wang T.","year":"2017","unstructured":"T. Wang , J. Blocki , N. Li , and S. Jha . Locally differentially private protocols for frequency estimation . In 26th {USENIX} Security Symposium ({USENIX} Security 17) , pages 729 -- 745 , 2017 . T. Wang, J. Blocki, N. Li, and S. Jha. Locally differentially private protocols for frequency estimation. In 26th {USENIX} Security Symposium ({USENIX} Security 17), pages 729--745, 2017."},{"key":"e_1_2_1_51_1","volume-title":"A comprehensive survey on local differential privacy toward data statistics and analysis in crowdsensing. CoRR, abs\/2010.05253","author":"Wang T.","year":"2020","unstructured":"T. Wang , X. Zhang , J. Feng , and X. Yang . A comprehensive survey on local differential privacy toward data statistics and analysis in crowdsensing. CoRR, abs\/2010.05253 , 2020 . T. Wang, X. Zhang, J. Feng, and X. Yang. A comprehensive survey on local differential privacy toward data statistics and analysis in crowdsensing. CoRR, abs\/2010.05253, 2020."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.247"},{"key":"e_1_2_1_53_1","volume-title":"Local differential privacy and its applications: A comprehensive survey. CoRR, abs\/2008.03686","author":"Yang M.","year":"2020","unstructured":"M. Yang , L. Lyu , J. Zhao , T. Zhu , and K. Lam . Local differential privacy and its applications: A comprehensive survey. CoRR, abs\/2008.03686 , 2020 . M. Yang, L. Lyu, J. Zhao, T. Zhu, and K. Lam. Local differential privacy and its applications: A comprehensive survey. CoRR, abs\/2008.03686, 2020."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3362032"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3134428"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3547305.3547312","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:12:22Z","timestamp":1672225942000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3547305.3547312"}},"subtitle":["one-shot and streaming"],"short-title":[],"issued":{"date-parts":[[2022,6]]},"references-count":55,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["10.14778\/3547305.3547312"],"URL":"http:\/\/dx.doi.org\/10.14778\/3547305.3547312","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,6]]}}}