{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T20:55:40Z","timestamp":1763499340671,"version":"3.45.0"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,11,13]],"date-time":"2022-11-13T00:00:00Z","timestamp":1668297600000},"content-version":"vor","delay-in-days":366,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["IIS-1652131, BIGDATA-1838177"],"award-info":[{"award-number":["IIS-1652131, BIGDATA-1838177"]}]},{"name":"AFOSR-YIP","award":["FA9550-18-1-0152"],"award-info":[{"award-number":["FA9550-18-1-0152"]}]},{"name":"ONR","award":["DURIP Grant, BRC grant on Randomized Numerical Linear Algebra"],"award-info":[{"award-number":["DURIP Grant, BRC grant on Randomized Numerical Linear Algebra"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,11,12]]},"DOI":"10.1145\/3460120.3485255","type":"proceedings-article","created":{"date-parts":[[2021,11,13]],"date-time":"2021-11-13T12:05:33Z","timestamp":1636805133000},"page":"3252-3265","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["A One-Pass Distributed and Private Sketch for Kernel Sums with Applications to Machine Learning at Scale"],"prefix":"10.1145","author":[{"given":"Benjamin","family":"Coleman","sequence":"first","affiliation":[{"name":"Rice University, Houston, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anshumali","family":"Shrivastava","sequence":"additional","affiliation":[{"name":"Rice University, Houston, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,11,13]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Felix Xinnan X Yu, Sanjiv Kumar, and Brendan McMahan.","author":"Agarwal Naman","year":"2018","unstructured":"Naman Agarwal, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Brendan McMahan. 2018. cpsgd: Communication-efficient and differentially-private distributed sgd. In Advances in Neural Information Processing Systems. 7564--7575."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213562"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v31i1.10884"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_3_2_1_5_1","volume-title":"International Conference on Machine Learning. 414--422","author":"Balog Matej","year":"2018","unstructured":"Matej Balog, Ilya Tolstikhin, and Bernhard Sch\u00f6lkopf. 2018. Differentially Private Database Release via Kernel Mean Embeddings. In International Conference on Machine Learning. 414--422."},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the 37th International Conference on Machine Learning (Proceedings of Machine Learning Research","author":"Bassily Raef","year":"2020","unstructured":"Raef Bassily, Albert Cheu, Shay Moran, Aleksandar Nikolov, Jonathan Ullman, and Steven Wu. 2020. Private Query Release Assisted by Public Data. In Proceedings of the 37th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 119), , Hal Daum\u00e9 III and Aarti Singh (Eds.). PMLR, 695--703. http:\/\/proceedings.mlr.press\/v119\/bassily20a.html"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3133982"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2021036"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095201"},{"key":"e_1_3_2_1_10_1","volume-title":"Todd J Treangen, and Anshumali Shrivastava.","author":"Coleman Benjamin","year":"2019","unstructured":"Benjamin Coleman, Benito Geordie, Li Chou, RA Leo Elworth, Todd J Treangen, and Anshumali Shrivastava. 2019. Diversified RACE Sampling on Data Streams Applied to Metagenomic Sequence Analysis. bioRxiv (2019), 852889."},{"key":"e_1_3_2_1_11_1","volume-title":"STORM: Foundations of End-to-End Empirical Risk Minimization on the Edge. arXiv preprint arXiv:2006.14554","author":"Coleman Benjamin","year":"2020","unstructured":"Benjamin Coleman, Gaurav Gupta, John Chen, and Anshumali Shrivastava. 2020. STORM: Foundations of End-to-End Empirical Risk Minimization on the Edge. arXiv preprint arXiv:2006.14554 (2020)."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380244"},{"volume-title":"Introduction to derivative-free optimization","author":"Conn Andrew R","key":"e_1_3_2_1_13_1","unstructured":"Andrew R Conn, Katya Scheinberg, and Luis N Vicente. 2009. Introduction to derivative-free optimization. Vol. 8. Siam."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3197390"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11787006_1"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11761679_29"},{"key":"e_1_3_2_1_17_1","volume-title":"et almbox","author":"Dwork Cynthia","year":"2014","unstructured":"Cynthia Dwork, Aaron Roth, et almbox. 2014. The algorithmic foundations of differential privacy. Foundations and Trends\u00ae in Theoretical Computer Science , Vol. 9, 3--4 (2014), 211--407."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660348"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813677"},{"volume-title":"23rd $$USENIX$$ Security Symposium ($$USENIX$$ Security 14) . 17--32.","author":"Fredrikson Matthew","key":"e_1_3_2_1_20_1","unstructured":"Matthew Fredrikson, Eric Lantz, Somesh Jha, Simon Lin, David Page, and Thomas Ristenpart. 2014. Privacy in pharmacogenetics: An end-to-end case study of personalized warfarin dosing. In 23rd $$USENIX$$ Security Symposium ($$USENIX$$ Security 14) . 17--32."},{"key":"e_1_3_2_1_21_1","first-page":"518","article-title":"Similarity search in high dimensions via hashing","volume":"99","author":"Gionis Aristides","year":"1999","unstructured":"Aristides Gionis, Piotr Indyk, Rajeev Motwani, et almbox. 1999. Similarity search in high dimensions via hashing. In Vldb, Vol. 99. 518--529.","journal-title":"Vldb"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2567709.2502603"},{"key":"e_1_3_2_1_23_1","unstructured":"Moritz Hardt Katrina Ligett and Frank McSherry. 2012. A simple and practical algorithm for differentially private data release. In Advances in Neural Information Processing Systems. 2339--2347."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"volume-title":"Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence (Montr\u00e9al","author":"George","key":"e_1_3_2_1_25_1","unstructured":"George H. John and Pat Langley. 1995. Estimating Continuous Distributions in Bayesian Classifiers. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence (Montr\u00e9al, Qu\u00e9, Canada) (UAI'95). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 338--345."},{"key":"e_1_3_2_1_26_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data ."},{"key":"e_1_3_2_1_27_1","volume-title":"Privacy for free: Communication-efficient learning with differential privacy using sketches. arXiv preprint arXiv:1911.00972","author":"Li Tian","year":"2019","unstructured":"Tian Li, Zaoxing Liu, Vyas Sekar, and Virginia Smith. 2019. Privacy for free: Communication-efficient learning with differential privacy using sketches. arXiv preprint arXiv:1911.00972 (2019)."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2020.2975749"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186056"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3054779"},{"key":"e_1_3_2_1_31_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning (Proceedings of Machine Learning Research","volume":"4604","author":"Mirshani Ardalan","year":"2019","unstructured":"Ardalan Mirshani, Matthew Reimherr, and Aleksandra Slavkovi\u0107. 2019. Formal Privacy for Functional Data with Gaussian Perturbations. In Proceedings of the 36th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 97). PMLR, Long Beach, California, USA, 4595--4604. http:\/\/proceedings.mlr.press\/v97\/mirshani19a.html"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556576"},{"key":"e_1_3_2_1_33_1","volume-title":"International Conference on Machine Learning. PMLR, 8253--8265","author":"Rothchild Daniel","year":"2020","unstructured":"Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, Ion Stoica, Vladimir Braverman, Joseph Gonzalez, and Raman Arora. 2020. Fetchsgd: Communication-efficient federated learning with sketching. In International Conference on Machine Learning. PMLR, 8253--8265."},{"key":"e_1_3_2_1_34_1","volume-title":"International Conference on Machine Learning . 3105--3114","author":"Sheffet Or","year":"2017","unstructured":"Or Sheffet. 2017. Differentially private ordinary least squares. In International Conference on Machine Learning . 3105--3114."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2017.41"},{"key":"e_1_3_2_1_36_1","unstructured":"Anshumali Shrivastava and Ping Li. 2014. Asymmetric LSH (ALSH) for sublinear time maximum inner product search (MIPS). In Advances in Neural Information Processing Systems. 2321--2329."},{"key":"e_1_3_2_1_37_1","unstructured":"Alexander Strehl and Joydeep Ghosh. 2000. Impact of similarity measures on web-page clustering. In AAAI-2000: Workshop of Artificial Intelligence for Web Search ."},{"key":"e_1_3_2_1_38_1","article-title":"Learning with privacy at scale","volume":"1","author":"Privacy Team Apple Differential","year":"2017","unstructured":"Apple Differential Privacy Team. 2017. Learning with privacy at scale. Apple Machine Learning Journal , Vol. 1, 8 (2017).","journal-title":"Apple Machine Learning Journal"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPRW.2019.00018"},{"key":"e_1_3_2_1_40_1","unstructured":"Jonathan Ullman. 2013. Answering N2"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488653"},{"key":"e_1_3_2_1_42_1","unstructured":"Jalaj Upadhyay. 2018. The price of privacy for low-rank factorization. In Advances in Neural Information Processing Systems. 4176--4187."},{"key":"e_1_3_2_1_43_1","volume-title":"Heng Tao Shen, et almbox","author":"Wang Jingdong","year":"2017","unstructured":"Jingdong Wang, Ting Zhang, Nicu Sebe, Heng Tao Shen, et almbox. 2017. A survey on learning to hash. IEEE transactions on pattern analysis and machine intelligence , Vol. 40, 4 (2017), 769--790."},{"key":"e_1_3_2_1_44_1","unstructured":"Yu-Xiang Wang. 2018. Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain (Proceedings of the Thirty-Fourth Conference on Uncertainty in Artificial Intelligence). Monterey California USA 93--103."},{"key":"e_1_3_2_1_45_1","volume-title":"International Conference on Machine Learning. 2493--2502","author":"Wang Yu-Xiang","year":"2015","unstructured":"Yu-Xiang Wang, Stephen Fienberg, and Alex Smola. 2015. Privacy for free: Posterior sampling and stochastic gradient monte carlo. In International Conference on Machine Learning. 2493--2502."},{"key":"e_1_3_2_1_46_1","unstructured":"Ziteng Wang Kai Fan Jiaqi Zhang and Liwei Wang. 2013. Efficient algorithm for privately releasing smooth queries. In Advances in Neural Information Processing Systems. 782--790."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1198\/jasa.2009.tm08651"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000060"},{"key":"e_1_3_2_1_49_1","volume-title":"Differentially private generative adversarial network. arXiv preprint arXiv:1802.06739","author":"Xie Liyang","year":"2018","unstructured":"Liyang Xie, Kaixiang Lin, Shu Wang, Fei Wang, and Jiayu Zhou. 2018. Differentially private generative adversarial network. arXiv preprint arXiv:1802.06739 (2018)."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0309-y"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3134428"}],"event":{"name":"CCS '21: 2021 ACM SIGSAC Conference on Computer and Communications Security","sponsor":["SIGSAC ACM Special Interest Group on Security, Audit, and Control"],"location":"Virtual Event Republic of Korea","acronym":"CCS '21"},"container-title":["Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460120.3485255","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3460120.3485255","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3460120.3485255","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T20:50:15Z","timestamp":1763499015000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460120.3485255"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,12]]},"references-count":51,"alternative-id":["10.1145\/3460120.3485255","10.1145\/3460120"],"URL":"https:\/\/doi.org\/10.1145\/3460120.3485255","relation":{},"subject":[],"published":{"date-parts":[[2021,11,12]]},"assertion":[{"value":"2021-11-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}