{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,10,6]],"date-time":"2022-10-06T12:44:47Z","timestamp":1665060287265},"publisher-location":"New York, NY, USA","reference-count":40,"publisher":"ACM","funder":[{"name":"Independent Research Fund Denmark (DFF)","award":["1051-00106B"]},{"name":"French National Research Agency (ANR)","award":["ANR-19-CE48-0016"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,8,14]]},"DOI":"10.1145\/3534678.3539409","type":"proceedings-article","created":{"date-parts":[[2022,8,12]],"date-time":"2022-08-12T19:06:12Z","timestamp":1660331172000},"source":"Crossref","is-referenced-by-count":0,"title":["Scalable Differentially Private Clustering via Hierarchically Separated Trees"],"prefix":"10.1145","author":[{"given":"Vincent","family":"Cohen-Addad","sequence":"first","affiliation":[{"name":"Google Research, Zurich, Switzerland"}]},{"given":"Alessandro","family":"Epasto","sequence":"additional","affiliation":[{"name":"Google Research, New-York City, NY, USA"}]},{"given":"Silvio","family":"Lattanzi","sequence":"additional","affiliation":[{"name":"Google Research, Zurich, Switzerland"}]},{"given":"Vahab","family":"Mirrokni","sequence":"additional","affiliation":[{"name":"Google Research, New-York City, NY, USA"}]},{"given":"Andres","family":"Munoz Medina","sequence":"additional","affiliation":[{"name":"Google Research, New-York City, NY, USA"}]},{"given":"David","family":"Saulpic","sequence":"additional","affiliation":[{"name":"Sorbonne Universit\u00e9, Paris, France"}]},{"given":"Chris","family":"Schwiegelshohn","sequence":"additional","affiliation":[{"name":"Aarhus University, Aarhus, Denmark"}]},{"given":"Sergei","family":"Vassilvitskii","sequence":"additional","affiliation":[{"name":"Google Research, New-York City, NY, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,8,14]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.15"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00070"},{"key":"e_1_3_2_2_3_1","volume-title":"Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 1027--1035","author":"Arthur David","year":"2007","unstructured":"David Arthur and Sergei Vassilvitskii . 2007 . k-means++: The advantages of careful seeding . In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 1027--1035 . David Arthur and Sergei Vassilvitskii. 2007. k-means++: The advantages of careful seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 1027--1035."},{"key":"e_1_3_2_2_4_1","unstructured":"Maria-Florina Balcan Travis Dick Yingyu Liang Wenlong Mou and Hongyang Zhang. 2017. Code of the algorithm described in Differentially Private Clustering in High-Dimensional Euclidean Spaces. https:\/\/github.com\/mouwenlong\/dpclustering-icml17 Maria-Florina Balcan Travis Dick Yingyu Liang Wenlong Mou and Hongyang Zhang. 2017. Code of the algorithm described in Differentially Private Clustering in High-Dimensional Euclidean Spaces. https:\/\/github.com\/mouwenlong\/dpclustering-icml17"},{"key":"e_1_3_2_2_5_1","volume-title":"Proceedings of the 34th International Conference on Machine Learning, ICML (Proceedings of Machine Learning Research","volume":"331","author":"Balcan Maria-Florina","year":"2017","unstructured":"Maria-Florina Balcan , Travis Dick , Yingyu Liang , Wenlong Mou , and Hongyang Zhang . 2017 . Differentially Private Clustering in High-Dimensional Euclidean Spaces . In Proceedings of the 34th International Conference on Machine Learning, ICML (Proceedings of Machine Learning Research , Vol. 70), Doina Precup and Yee Whye Teh (Eds.). PMLR, 322-- 331 . Maria-Florina Balcan, Travis Dick, Yingyu Liang, Wenlong Mou, and Hongyang Zhang. 2017. Differentially Private Clustering in High-Dimensional Euclidean Spaces. In Proceedings of the 34th International Conference on Machine Learning, ICML (Proceedings of Machine Learning Research, Vol. 70), Doina Precup and Yee Whye Teh (Eds.). PMLR, 322--331."},{"key":"e_1_3_2_2_6_1","volume-title":"Searching for exotic particles in high-energy physics with deep learning. Nature communications 5, 1","author":"Baldi Pierre","year":"2014","unstructured":"Pierre Baldi , Peter Sadowski , and Daniel Whiteson . 2014. Searching for exotic particles in high-energy physics with deep learning. Nature communications 5, 1 ( 2014 ), 1--9. Pierre Baldi, Peter Sadowski, and Daniel Whiteson. 2014. Searching for exotic particles in high-energy physics with deep learning. Nature communications 5, 1 (2014), 1--9."},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465224"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3125644"},{"key":"e_1_3_2_2_9_1","unstructured":"Rajen Bhatt and Abhinav Dhall. 2009. https:\/\/archive.ics.uci.edu\/ml\/datasets\/Skin+Segmentation Rajen Bhatt and Abhinav Dhall. 2009. https:\/\/archive.ics.uci.edu\/ml\/datasets\/Skin+Segmentation"},{"key":"e_1_3_2_2_10_1","volume-title":"Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables. Computers and electronics in agriculture 24, 3","author":"Blackard Jock A","year":"1999","unstructured":"Jock A Blackard and Denis J Dean . 1999. Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables. Computers and electronics in agriculture 24, 3 ( 1999 ), 131--151. Jock A Blackard and Denis J Dean. 1999. Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables. Computers and electronics in agriculture 24, 3 (1999), 131--151."},{"key":"e_1_3_2_2_11_1","volume-title":"Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 737--756","author":"Byrka Jaros\u0141aw","year":"2014","unstructured":"Jaros\u0141aw Byrka , Thomas Pensyl , Bartosz Rybicki , Aravind Srinivasan , and Khoa Trinh . 2014 . An improved approximation for k-median, and positive correlation in budgeted optimization . In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 737--756 . Jaros\u0141aw Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. 2014. An improved approximation for k-median, and positive correlation in budgeted optimization. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 737--756."},{"key":"e_1_3_2_2_12_1","volume-title":"Locally Private k-Means in One Round. CoRR abs\/2104.09734","author":"Chang Alisa","year":"2021","unstructured":"Alisa Chang , Badih Ghazi , Ravi Kumar , and Pasin Manurangsi . 2021. Locally Private k-Means in One Round. CoRR abs\/2104.09734 ( 2021 ). https:\/\/arxiv.org\/abs\/2104.09734 Alisa Chang, Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. 2021. Locally Private k-Means in One Round. CoRR abs\/2104.09734 (2021). https:\/\/arxiv.org\/abs\/2104.09734"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509965"},{"key":"e_1_3_2_2_14_1","volume-title":"Differentially private kmeans clustering via exponential mechanism and max cover. CoRR abs\/2009.01220","author":"Chaturvedi Anamay","year":"2020","unstructured":"Anamay Chaturvedi , Huy L. Nguyen , and Eric Xu. 2020. Differentially private kmeans clustering via exponential mechanism and max cover. CoRR abs\/2009.01220 ( 2020 ). https:\/\/arxiv.org\/abs\/2009.01220 Anamay Chaturvedi, Huy L. Nguyen, and Eric Xu. 2020. Differentially private kmeans clustering via exponential mechanism and max cover. CoRR abs\/2009.01220 (2020). https:\/\/arxiv.org\/abs\/2009.01220"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477541"},{"key":"e_1_3_2_2_16_1","volume-title":"Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021","author":"Cohen-Addad Vincent","year":"2021","unstructured":"Vincent Cohen-Addad , David Saulpic , and Chris Schwiegelshohn . 2021 . Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021 , NeurIPS 2021, December 6-14, 2021, virtual, Marc'Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and JenniferWortman Vaughan (Eds.). 21085--21098. https:\/\/proceedings.neurips.cc\/paper\/2021\/hash\/b035d6563a2adac9f822940c145263ce-Abstract.html Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. 2021. Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, Marc'Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and JenniferWortman Vaughan (Eds.). 21085--21098. https:\/\/proceedings.neurips.cc\/paper\/2021\/hash\/b035d6563a2adac9f822940c145263ce-Abstract.html"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_2_2_18_1","unstructured":"Dheeru Dua and Casey Graff. 2017. UCI Machine Learning Repository. http:\/\/archive.ics.uci.edu\/ml Dheeru Dua and Casey Graff. 2017. UCI Machine Learning Repository. http:\/\/archive.ics.uci.edu\/ml"},{"key":"e_1_3_2_2_19_1","first-page":"3","article-title":"The Algorithmic Foundations of Differential Privacy","volume":"9","author":"Dwork Cynthia","year":"2014","unstructured":"Cynthia Dwork and Aaron Roth . 2014 . The Algorithmic Foundations of Differential Privacy . Found. Trends Theor. Comput. Sci. 9 , 3 - 4 (2014), 211--407. https:\/\/doi.org\/10.1561\/0400000042 Cynthia Dwork and Aaron Roth. 2014. The Algorithmic Foundations of Differential Privacy. Found. Trends Theor. Comput. Sci. 9, 3-4 (2014), 211--407. https:\/\/doi.org\/10.1561\/0400000042","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780608"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536465"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"crossref","unstructured":"Pasi Fr\u00e4nti and Sami Sieranoja. 2018. K-means properties on six clustering benchmark datasets. 4743--4759 pages. http:\/\/cs.uef.fi\/sipu\/datasets\/ Pasi Fr\u00e4nti and Sami Sieranoja. 2018. K-means properties on six clustering benchmark datasets. 4743--4759 pages. http:\/\/cs.uef.fi\/sipu\/datasets\/","DOI":"10.1007\/s10489-018-1238-7"},{"key":"e_1_3_2_2_23_1","unstructured":"Badih Ghazi Ravi Kumar and Pasin Manurangsi. 2020. Differentially Private Clustering: Tight Approximation Ratios. In Advances in Neural Information Processing Systems Hugo Larochelle Marc'Aurelio Ranzato Raia Hadsell Maria-Florina Balcan and Hsuan-Tien Lin (Eds.). Badih Ghazi Ravi Kumar and Pasin Manurangsi. 2020. Differentially Private Clustering: Tight Approximation Ratios. In Advances in Neural Information Processing Systems Hugo Larochelle Marc'Aurelio Ranzato Raia Hadsell Maria-Florina Balcan and Hsuan-Tien Lin (Eds.)."},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25591-5_39"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"crossref","unstructured":"Sariel Har-Peled. 2011. Geometric approximation algorithms. Number 173. American Mathematical Soc. Sariel Har-Peled. 2011. Geometric approximation algorithms. Number 173. American Mathematical Soc.","DOI":"10.1090\/surv\/173"},{"key":"e_1_3_2_2_26_1","volume-title":"ACM SIGOPS operating systems review","author":"Isard Michael","unstructured":"Michael Isard , Mihai Budiu , Yuan Yu , Andrew Birrell , and Dennis Fetterly . 2007. Dryad: distributed data-parallel programs from sequential building blocks . In ACM SIGOPS operating systems review , Vol. 41 . ACM , 59--72. Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly. 2007. Dryad: distributed data-parallel programs from sequential building blocks. In ACM SIGOPS operating systems review, Vol. 41. ACM, 59--72."},{"key":"e_1_3_2_2_27_1","volume-title":"Towards Practical Differentially Private Convex Optimization. In 2019 IEEE Symposium on Security and Privacy, SP 2019","author":"Iyengar Roger","year":"2019","unstructured":"Roger Iyengar , Joseph P. Near , Dawn Song , Om Thakkar , Abhradeep Thakurta , and Lun Wang . 2019 . Towards Practical Differentially Private Convex Optimization. In 2019 IEEE Symposium on Security and Privacy, SP 2019 , San Francisco, CA, USA , May 19-23, 2019. IEEE, 299--316. Roger Iyengar, Joseph P. Near, Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang. 2019. Towards Practical Differentially Private Convex Optimization. In 2019 IEEE Symposium on Security and Privacy, SP 2019, San Francisco, CA, USA, May 19-23, 2019. IEEE, 299--316."},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/950620.950621"},{"key":"e_1_3_2_2_29_1","volume-title":"Nguyen","author":"Jones Matthew","year":"2021","unstructured":"Matthew Jones , Huy L. Nguyen , and Thy D . Nguyen . 2021 . Differentially Private Clustering via Maximum Coverage. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021. AAAI Press , 11555--11563. https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/17375 Matthew Jones, Huy L. Nguyen, and Thy D. Nguyen. 2021. Differentially Private Clustering via Maximum Coverage. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021. AAAI Press, 11555--11563. https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/17375"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.003"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873677"},{"key":"e_1_3_2_2_32_1","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Shi Li.","unstructured":"Shi Li. 2011. A 1.488 approximation algorithm for the uncapacitated facility location problem. In International Colloquium on Automata, Languages, and Programming . Springer , 77--88. Shi Li. 2011. A 1.488 approximation algorithm for the uncapacitated facility location problem. In International Colloquium on Automata, Languages, and Programming. Springer, 77--88."},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"e_1_3_2_2_34_1","volume-title":"Differentially Private k-Means Clustering with Guaranteed Convergence. CoRR abs\/2002.01043","author":"Lu Zhigang","year":"2020","unstructured":"Zhigang Lu and Hong Shen . 2020. Differentially Private k-Means Clustering with Guaranteed Convergence. CoRR abs\/2002.01043 ( 2020 ). https:\/\/arxiv.org\/abs\/2002.01043 Zhigang Lu and Hong Shen. 2020. Differentially Private k-Means Clustering with Guaranteed Convergence. CoRR abs\/2002.01043 (2020). https:\/\/arxiv.org\/abs\/2002.01043"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316350"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213876"},{"key":"e_1_3_2_2_37_1","volume-title":"Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016 (JMLR Workshop and Conference Proceedings","volume":"154","author":"Nock Richard","year":"2016","unstructured":"Richard Nock , Rapha\u00ebl Canyasse , Roksana Boreli , and Frank Nielsen . 2016 . kvariates++: more pluses in the k-means++ . In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016 (JMLR Workshop and Conference Proceedings , Vol. 48), Maria-Florina Balcan and Kilian Q. Weinberger (Eds.). JMLR.org, 145-- 154 . Richard Nock, Rapha\u00ebl Canyasse, Roksana Boreli, and Frank Nielsen. 2016. kvariates++: more pluses in the k-means++. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016 (JMLR Workshop and Conference Proceedings, Vol. 48), Maria-Florina Balcan and Kilian Q. Weinberger (Eds.). JMLR.org, 145--154."},{"key":"e_1_3_2_2_38_1","volume-title":"Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018","author":"Stemmer Uri","year":"2018","unstructured":"Uri Stemmer and Haim Kaplan . 2018 . Differentially Private k-Means with Constant Multiplicative Error . In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018 , NeurIPS 2018, December 3-8, 2018, Montr\u00e9al, Canada, Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicol\u00f2 Cesa-Bianchi, and Roman Garnett (Eds.). 5436--5446. https:\/\/proceedings.neurips.cc\/paper\/2018\/hash\/32b991e5d77ad140559ffb95522992d0-Abstract.html Uri Stemmer and Haim Kaplan. 2018. Differentially Private k-Means with Constant Multiplicative Error. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montr\u00e9al, Canada, Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicol\u00f2 Cesa-Bianchi, and Roman Garnett (Eds.). 5436--5446. https:\/\/proceedings.neurips.cc\/paper\/2018\/hash\/32b991e5d77ad140559ffb95522992d0-Abstract.html"},{"key":"e_1_3_2_2_39_1","volume-title":"Hadoop: The definitive guide. \"O'Reilly Media","author":"White Tom","year":"2012","unstructured":"Tom White . 2012 . Hadoop: The definitive guide. \"O'Reilly Media , Inc .\". Tom White. 2012. Hadoop: The definitive guide. \"O'Reilly Media, Inc.\"."},{"key":"e_1_3_2_2_40_1","first-page":"10","article-title":"Spark: Cluster computing with working sets","volume":"10","author":"Zaharia Matei","year":"2010","unstructured":"Matei Zaharia , Mosharaf Chowdhury , Michael J Franklin , Scott Shenker , and Ion Stoica . 2010 . Spark: Cluster computing with working sets . HotCloud 10 , 10 -- 10 (2010), 95. Matei Zaharia, Mosharaf Chowdhury, Michael J Franklin, Scott Shenker, and Ion Stoica. 2010. Spark: Cluster computing with working sets. HotCloud 10, 10--10 (2010), 95.","journal-title":"HotCloud"}],"event":{"name":"KDD '22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","location":"Washington DC USA","acronym":"KDD '22","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data"]},"container-title":["Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3534678.3539409","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,6]],"date-time":"2022-10-06T12:14:17Z","timestamp":1665058457000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3534678.3539409"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,14]]},"references-count":40,"alternative-id":["10.1145\/3534678.3539409","10.1145\/3534678"],"URL":"http:\/\/dx.doi.org\/10.1145\/3534678.3539409","relation":{},"published":{"date-parts":[[2022,8,14]]}}}