{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:18:10Z","timestamp":1779175090125,"version":"3.51.4"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T00:00:00Z","timestamp":1731024000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"HKRGC","award":["16201318, 16201819, and 16205420"],"award-info":[{"award-number":["16201318, 16201819, and 16205420"]}]},{"name":"National Science Foundation","award":["2016393"],"award-info":[{"award-number":["2016393"]}]},{"name":"DARPA and SPAWAR","award":["N66001-15-C-4067"],"award-info":[{"award-number":["N66001-15-C-4067"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"<jats:p>\n            Answering SPJA queries under differential privacy (DP), including graph pattern counting under node-DP as an important special case, has received considerable attention in recent years. The dual challenge of foreign-key constraints combined with self-joins is particularly tricky to deal with, and no existing DP mechanisms can correctly handle both. For the special case of graph pattern counting under node-DP, the existing mechanisms are correct (i.e., satisfy DP), but they do not offer nontrivial utility guarantees or are very complicated and costly. In this article, we propose two mechanisms for solving this problem with both efficiency and strong utility guarantees. The first mechanism, called\n            <jats:italic>R2T<\/jats:italic>\n            , is simple and efficient, while achieving\n            <jats:italic>down-neighborhood optimality<\/jats:italic>\n            with a logarithmic optimality ratio. Down-neighborhood optimality is a new notion of optimality that we introduce for measuring the utilities of DP mechanisms, which can be considered as a natural relaxation of instance optimality, and it is especially suitable for functions with a large or unbounded sensitivity. Our second mechanism further reduces the optimality ratio to a double logarithm, which is also known to be optimal, thus we call this mechanism\n            <jats:italic>OPT<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            . While OPT\n            <jats:sup>2<\/jats:sup>\n            also runs in polynomial time, it does have a higher computational cost than R2T in practice. Both R2T and OPT\n            <jats:sup>2<\/jats:sup>\n            are simple enough that they can be easily implemented on top of any RDBMS and an LP solver. Experimental results show that they offer order-of-magnitude improvements in terms of utility over existing techniques, even those specifically designed for graph pattern counting.\n          <\/jats:p>","DOI":"10.1145\/3697831","type":"journal-article","created":{"date-parts":[[2024,9,26]],"date-time":"2024-09-26T11:14:32Z","timestamp":1727349272000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Instance-optimal Truncation for Differentially Private Query Evaluation with Foreign Keys"],"prefix":"10.1145","volume":"49","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0394-4125","authenticated-orcid":false,"given":"Wei","family":"Dong","sequence":"first","affiliation":[{"name":"College of Computing and Data Science, Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9038-0585","authenticated-orcid":false,"given":"Juanru","family":"Fang","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, The Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2178-3716","authenticated-orcid":false,"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, The Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2101-3973","authenticated-orcid":false,"given":"Yuchao","family":"Tao","sequence":"additional","affiliation":[{"name":"Duke University, Durham, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1555-7330","authenticated-orcid":false,"given":"Ashwin","family":"Machanavajjhala","sequence":"additional","affiliation":[{"name":"Computer Science, Duke University, Durham, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,11,8]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1145\/2976749.2978318","volume-title":"Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security","author":"Abadi Martin","year":"2016","unstructured":"Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. 2016. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 308\u2013318."},{"key":"e_1_3_2_3_2","first-page":"263","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Amin Kareem","year":"2019","unstructured":"Kareem Amin, Alex Kulesza, Andres Munoz, and Sergei Vassilvtiskii. 2019. Bounding user contributions: A bias-variance trade-off in differential privacy. In Proceedings of the International Conference on Machine Learning. 263\u2013271."},{"key":"e_1_3_2_4_2","article-title":"Differentially private learning with adaptive clipping","author":"Andrew Galen","year":"2019","unstructured":"Galen Andrew, Om Thakkar, H. Brendan McMahan, and Swaroop Ramaswamy. 2019. Differentially private learning with adaptive clipping. arXiv preprint arXiv:1905.03871 (2019).","journal-title":"arXiv preprint arXiv:1905.03871"},{"key":"e_1_3_2_5_2","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP\u201916)","author":"Arapinis Myrto","year":"2016","unstructured":"Myrto Arapinis, Diego Figueira, and Marco Gaboardi. 2016. Sensitivity of counting queries. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP\u201916)."},{"key":"e_1_3_2_6_2","article-title":"Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms","volume":"33","author":"Asi Hilal","year":"2020","unstructured":"Hilal Asi and John C. Duchi. 2020. Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms. Advances in Neural Information Processing Systems 33 (2020), 1\u201312.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_7_2","first-page":"273","volume-title":"Proceedings of the 26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems","author":"Barak Boaz","year":"2007","unstructured":"Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank McSherry, and Kunal Talwar. 2007. Privacy, accuracy, and consistency too: A holistic solution to contingency table release. In Proceedings of the 26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. 273\u2013282."},{"key":"e_1_3_2_8_2","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1109\/FOCS.2014.56","volume-title":"Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science","author":"Bassily Raef","year":"2014","unstructured":"Raef Bassily, Adam Smith, and Abhradeep Thakurta. 2014. Private empirical risk minimization: Efficient algorithms and tight error bounds. In Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. IEEE, 464\u2013473."},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","first-page":"2480","DOI":"10.1137\/1.9781611975482.152","volume-title":"Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"B\u0142asiok Jaroslaw","year":"2019","unstructured":"Jaroslaw B\u0142asiok, Mark Bun, Aleksandar Nikolov, and Thomas Steinke. 2019. Towards instance-optimal private query release. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms. 2480\u20132497."},{"key":"e_1_3_2_10_2","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1145\/2422436.2422449","volume-title":"Proceedings of the 4th Conference on Innovations in Theoretical Computer Science","author":"Blocki Jeremiah","year":"2013","unstructured":"Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. 2013. Differentially private data analysis of social networks via restricted sensitivity. In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science. 87\u201396."},{"issue":"2","key":"e_1_3_2_11_2","first-page":"1","article-title":"PrivLava: Synthesizing relational data with foreign keys under differential privacy","volume":"1","author":"Cai Kuntai","year":"2023","unstructured":"Kuntai Cai, Xiaokui Xiao, and Graham Cormode. 2023. PrivLava: Synthesizing relational data with foreign keys under differential privacy. Proceedings of the ACM on Management of Data 1, 2 (2023), 1\u201325.","journal-title":"Proceedings of the ACM on Management of Data"},{"key":"e_1_3_2_12_2","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1145\/2463676.2465304","volume-title":"Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data","author":"Chen Shixi","year":"2013","unstructured":"Shixi Chen and Shuigeng Zhou. 2013. Recursive mechanism: Towards node differential privacy and unrestricted joins. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. 653\u2013664."},{"key":"e_1_3_2_13_2","first-page":"123","volume-title":"Proceedings of the 2016 International Conference on Management of Data","author":"Day Wei-Yen","year":"2016","unstructured":"Wei-Yen Day, Ninghui Li, and Min Lyu. 2016. Publishing graph degree distribution with node differential privacy. In Proceedings of the 2016 International Conference on Management of Data. 123\u2013138."},{"key":"e_1_3_2_14_2","unstructured":"Apple Differential Privacy Team. n.d. Learning with Privacy at Scale. Retrieved September 27 2024 from https:\/\/docs-assets.developer.apple.com\/ml-research\/papers\/learning-with-privacy-at-scale.pdf"},{"key":"e_1_3_2_15_2","volume-title":"Proceedings of the 31st International Conference on Neural Information Processing Systems (NIPS\u201917)","author":"Ding Bolin","year":"2017","unstructured":"Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. 2017. Collecting telemetry data privately. In Proceedings of the 31st International Conference on Neural Information Processing Systems (NIPS\u201917). 3574\u20133583."},{"issue":"3","key":"e_1_3_2_16_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3654931","article-title":"Continual observation of joins under differential privacy","volume":"2","author":"Dong Wei","year":"2024","unstructured":"Wei Dong, Zijun Chen, Qiyao Luo, Elaine Shi, and Ke Yi. 2024. Continual observation of joins under differential privacy. Proceedings of the ACM on Management of Data 2, 3 (2024), 1\u201327.","journal-title":"Proceedings of the ACM on Management of Data"},{"key":"e_1_3_2_17_2","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1145\/3514221.3517844","volume-title":"Proceedings of the 2022 International Conference on Management of Data","author":"Dong Wei","year":"2022","unstructured":"Wei Dong, Juanru Fang, Ke Yi, Yuchao Tao, and Ashwin Machanavajjhala. 2022. R2T: Instance-optimal truncation for differentially private query evaluation with foreign keys. In Proceedings of the 2022 International Conference on Management of Data. 759\u2013772."},{"key":"e_1_3_2_18_2","doi-asserted-by":"crossref","first-page":"2190","DOI":"10.1109\/SP46215.2023.10179466","volume-title":"Proceedings of the 2023 IEEE Symposium on Security and Privacy (SP\u201923)","author":"Dong Wei","year":"2023","unstructured":"Wei Dong, Qiyao Luo, and Ke Yi. 2023. Continual observation under user-level differential privacy. In Proceedings of the 2023 IEEE Symposium on Security and Privacy (SP\u201923). IEEE, 2190\u20132207."},{"issue":"2","key":"e_1_3_2_19_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3589268","article-title":"Better than composition: How to answer multiple relational queries under differential privacy","volume":"1","author":"Dong Wei","year":"2023","unstructured":"Wei Dong, Dajun Sun, and Ke Yi. 2023. Better than composition: How to answer multiple relational queries under differential privacy. Proceedings of the ACM on Management of Data 1, 2 (2023), 1\u201326.","journal-title":"Proceedings of the ACM on Management of Data"},{"key":"e_1_3_2_20_2","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Dong Wei","year":"2021","unstructured":"Wei Dong and Ke Yi. 2021. Residual sensitivity for differentially private multi-way joins. In Proceedings of the ACM SIGMOD International Conference on Management of Data."},{"key":"e_1_3_2_21_2","volume-title":"Proceedings of the ACM Symposium on Principles of Database Systems","author":"Dong Wei","year":"2022","unstructured":"Wei Dong and Ke Yi. 2022. A nearly instance-optimal differentially private mechanism for conjunctive queries. In Proceedings of the ACM Symposium on Principles of Database Systems."},{"issue":"3","key":"e_1_3_2_22_2","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1145\/3631504.3631506","article-title":"Query evaluation under differential privacy","volume":"52","author":"Dong Wei","year":"2023","unstructured":"Wei Dong and Ke Yi. 2023. Query evaluation under differential privacy. ACM SIGMOD Record 52, 3 (2023), 6\u201317.","journal-title":"ACM SIGMOD Record"},{"key":"e_1_3_2_23_2","volume-title":"Proceedings of the ACM Symposium on Principles of Database Systems","author":"Dong Wei","year":"2023","unstructured":"Wei Dong and Ke Yi. 2023. Universal private estimators. In Proceedings of the ACM Symposium on Principles of Database Systems."},{"key":"e_1_3_2_24_2","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1145\/3584372.3588669","volume-title":"Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems","author":"Dong Wei","year":"2023","unstructured":"Wei Dong and Ke Yi. 2023. Universal private estimators. In Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. 195\u2013206."},{"key":"e_1_3_2_25_2","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/11681878_14","volume-title":"Proceedings of the Theory of Cryptography Conference","author":"Dwork Cynthia","year":"2006","unstructured":"Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Calibrating noise to sensitivity in private data analysis. In Proceedings of the Theory of Cryptography Conference. 265\u2013284."},{"key":"e_1_3_2_26_2","first-page":"381","volume-title":"Proceedings of the 41st Annual ACM Symposium on Theory of Computing","author":"Dwork Cynthia","year":"2009","unstructured":"Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil Vadhan. 2009. On the complexity of differentially private data release: Efficient algorithms and hardness results. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing(STOC\u201909). ACM, New York, NY, USA, 381\u2013390. DOI:10.1145\/1536414.1536467"},{"issue":"3","key":"e_1_3_2_27_2","first-page":"211","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. Foundations and Trends\u00ae in Theoretical Computer Science 9, 3-4 (2014), 211\u2013407.","journal-title":"Foundations and Trends\u00ae in Theoretical Computer Science"},{"key":"e_1_3_2_28_2","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.1145\/2660267.2660348","volume-title":"Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security","author":"Erlingsson \u00dalfar","year":"2014","unstructured":"\u00dalfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. 2014. RAPPOR: Randomized aggregatable privacy-preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. 1054\u20131067."},{"key":"e_1_3_2_29_2","doi-asserted-by":"crossref","unstructured":"Juanru Fang Wei Dong and Ke Yi. 2022. Shifted inverse: A general mechanism for monotonic functions under user differential privacy. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 1009\u20131022.","DOI":"10.1145\/3548606.3560567"},{"key":"e_1_3_2_30_2","first-page":"2339","volume-title":"Advances in Neural Information Processing Systems","author":"Hardt Moritz","year":"2012","unstructured":"Moritz Hardt, Katrina Ligett, and Frank McSherry. 2012. A simple and practical algorithm for differentially private data release. Advances in Neural Information Processing Systems 25 (2012), 2339\u20132347."},{"key":"e_1_3_2_31_2","volume-title":"Proceedings of the 35th Conference on Neural Information Processing Systems (NeurIPS\u201921)","author":"Huang Ziyue","year":"2021","unstructured":"Ziyue Huang, Yuting Liang, and Ke Yi. 2021. Instance-optimal mean estimation under differential privacy. In Proceedings of the 35th Conference on Neural Information Processing Systems (NeurIPS\u201921). 1\u201312."},{"issue":"5","key":"e_1_3_2_32_2","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1145\/3187009.3177733","article-title":"Towards practical differential privacy for SQL queries","volume":"11","author":"Johnson Noah","year":"2018","unstructured":"Noah Johnson, Joseph P. Near, and Dawn Song. 2018. Towards practical differential privacy for SQL queries. Proceedings of the VLDB Endowment 11, 5 (2018), 526\u2013539.","journal-title":"Proceedings of the VLDB Endowment"},{"issue":"11","key":"e_1_3_2_33_2","doi-asserted-by":"crossref","first-page":"1146","DOI":"10.14778\/3402707.3402749","article-title":"Private analysis of graph structure","volume":"4","author":"Karwa Vishesh","year":"2011","unstructured":"Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, and Grigory Yaroslavtsev. 2011. Private analysis of graph structure. Proceedings of the VLDB Endowment 4, 11 (2011), 1146\u20131157.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_3_2_34_2","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1007\/978-3-642-36594-2_26","volume-title":"Proceedings of the Theory of Cryptography Conference","author":"Kasiviswanathan Shiva Prasad","year":"2013","unstructured":"Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. 2013. Analyzing graphs with node differential privacy. In Proceedings of the Theory of Cryptography Conference. 457\u2013476."},{"issue":"11","key":"e_1_3_2_35_2","doi-asserted-by":"crossref","first-page":"1371","DOI":"10.14778\/3342263.3342274","article-title":"PrivateSQL: A differentially private SQL query engine","volume":"12","author":"Kotsogiannis Ios","year":"2019","unstructured":"Ios Kotsogiannis, Yuchao Tao, Xi He, Maryam Fanaeepour, Ashwin Machanavajjhala, Michael Hay, and Gerome Miklau. 2019. PrivateSQL: A differentially private SQL query engine. Proceedings of the VLDB Endowment 12, 11 (2019), 1371\u20131384.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_3_2_36_2","unstructured":"Jure Leskovec and Andrej Krevl. 2016. SNAP Datasets: Stanford Large Network Dataset Collection (2014). Retrieved September 27 2024 fromhttps:\/\/snap.stanford.edu\/data"},{"issue":"6","key":"e_1_3_2_37_2","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1007\/s00778-015-0398-x","article-title":"The matrix mechanism: Optimizing linear counting queries under differential privacy","volume":"24","author":"Li Chao","year":"2015","unstructured":"Chao Li, Gerome Miklau, Michael Hay, Andrew McGregor, and Vibhor Rastogi. 2015. The matrix mechanism: Optimizing linear counting queries under differential privacy. VLDB Journal 24, 6 (2015), 757\u2013781.","journal-title":"VLDB Journal"},{"key":"e_1_3_2_38_2","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming","author":"Lund C.","year":"1993","unstructured":"C. Lund and M. Yannakakis. 1993. The approximation of maximum subgraph problems. In Proceedings of the International Colloquium on Automata, Languages, and Programming."},{"key":"e_1_3_2_39_2","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1109\/ICDE.2008.4497436","volume-title":"Proceedings of the 2008 IEEE 24th International Conference on Data Engineering","author":"Machanavajjhala Ashwin","year":"2008","unstructured":"Ashwin Machanavajjhala, Daniel Kifer, John Abowd, Johannes Gehrke, and Lars Vilhuber. 2008. Privacy: Theory meets practice on the map. In Proceedings of the 2008 IEEE 24th International Conference on Data Engineering. IEEE, 277\u2013286."},{"key":"e_1_3_2_40_2","article-title":"Learning differentially private recurrent language models","author":"McMahan H. Brendan","year":"2017","unstructured":"H. Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. 2017. Learning differentially private recurrent language models. arXiv preprint arXiv:1710.06963 (2017).","journal-title":"arXiv preprint arXiv:1710.06963"},{"key":"e_1_3_2_41_2","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1145\/1559845.1559850","volume-title":"Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data","author":"McSherry Frank D.","year":"2009","unstructured":"Frank D. McSherry. 2009. Privacy integrated queries: An extensible platform for privacy-preserving data analysis. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. 19\u201330."},{"key":"e_1_3_2_42_2","first-page":"149","volume-title":"Proceedings of the USENIX Symposium on Operating Systems Design and Implementation","author":"Narayan Arjun","year":"2012","unstructured":"Arjun Narayan and Andreas Haeberlen. 2012. DJoin: Differentially private join queries over distributed databases. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation. 149\u2013162."},{"key":"e_1_3_2_43_2","first-page":"351","volume-title":"Proceedings of the 45th Annual ACM Symposium on Theory of Computing","author":"Nikolov Aleksandar","year":"2013","unstructured":"Aleksandar Nikolov, Kunal Talwar, and Li Zhang. 2013. The geometry of differential privacy: The sparse and approximate cases. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing. 351\u2013360."},{"key":"e_1_3_2_44_2","first-page":"75","volume-title":"Proceedings of the 39th Annual ACM Symposium on Theory of Computing","author":"Nissim Kobbi","year":"2007","unstructured":"Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. 2007. Smooth sensitivity and sampling in private data analysis. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing. 75\u201384."},{"key":"e_1_3_2_45_2","volume-title":"Proceedings of the 10th Workshop on Quantitative Aspects of Programming Languages (QAPL\u201912)","author":"Palamidessi Catuscia","year":"2012","unstructured":"Catuscia Palamidessi and Marco Stronati. 2012. Differential privacy for relational algebra: Improving the sensitivity bounds via constraint systems. In Proceedings of the 10th Workshop on Quantitative Aspects of Programming Languages (QAPL\u201912). 92\u2013105."},{"key":"e_1_3_2_46_2","article-title":"AdaCliP: Adaptive clipping for private SGD","author":"Pichapati Venkatadheeraj","year":"2019","unstructured":"Venkatadheeraj Pichapati, Ananda Theertha Suresh, Felix X. Yu, Sashank J. Reddi, and Sanjiv Kumar. 2019. AdaCliP: Adaptive clipping for private SGD. arXiv preprint arXiv:1908.07643 (2019).","journal-title":"arXiv preprint arXiv:1908.07643"},{"issue":"8","key":"e_1_3_2_47_2","article-title":"Calibrating data to sensitivity in private data analysis","volume":"7","author":"Proserpio Davide","year":"2014","unstructured":"Davide Proserpio, Sharon Goldberg, and Frank McSherry. 2014. Calibrating data to sensitivity in private data analysis. Proceedings of the VLDB Endowment 7, 8 (2014), 637\u2013648.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_3_2_48_2","doi-asserted-by":"crossref","first-page":"1435","DOI":"10.1145\/2588555.2588575","volume-title":"Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data","author":"Qardaji Wahbeh","year":"2014","unstructured":"Wahbeh Qardaji, Weining Yang, and Ninghui Li. 2014. Practical differentially private release of marginal contingency tables. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. 1435\u20131446."},{"issue":"14","key":"e_1_3_2_49_2","doi-asserted-by":"crossref","first-page":"1954","DOI":"10.14778\/2556549.2556576","article-title":"Understanding hierarchical methods for differentially private histograms","volume":"6","author":"Qardaji Wahbeh","year":"2013","unstructured":"Wahbeh Qardaji, Weining Yang, and Ninghui Li. 2013. Understanding hierarchical methods for differentially private histograms. Proceedings of the VLDB Endowment 6, 14 (2013), 1954\u20131965.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_3_2_50_2","first-page":"245","volume-title":"Proceedings of the 2013 IEEE Global Conference on Signal and Information Processing","author":"Song Shuang","year":"2013","unstructured":"Shuang Song, Kamalika Chaudhuri, and Anand D. Sarwate. 2013. Stochastic gradient descent with differentially private updates. In Proceedings of the 2013 IEEE Global Conference on Signal and Information Processing. IEEE, 245\u2013248."},{"issue":"1","key":"e_1_3_2_51_2","first-page":"7964","article-title":"Locally private k-means clustering","volume":"22","author":"Stemmer Uri","year":"2021","unstructured":"Uri Stemmer. 2021. Locally private k-means clustering. Journal of Machine Learning Research 22, 1 (2021), 7964\u20137993.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_52_2","article-title":"Differentially private k-means with constant multiplicative error","volume":"31","author":"Stemmer Uri","year":"2018","unstructured":"Uri Stemmer and Haim Kaplan. 2018. Differentially private k-means with constant multiplicative error. Advances in Neural Information Processing Systems 31 (2018), 1\u201311.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_53_2","first-page":"479","volume-title":"Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data","author":"Tao Yuchao","year":"2020","unstructured":"Yuchao Tao, Xi He, Ashwin Machanavajjhala, and Sudeepa Roy. 2020. Computing local sensitivities of counting queries with joins. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 479\u2013494."},{"key":"e_1_3_2_54_2","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/978-3-319-57048-8_7","volume-title":"Tutorials on the Foundations of Cryptography","author":"Vadhan Salil","year":"2017","unstructured":"Salil Vadhan. 2017. The complexity of differential privacy. In Tutorials on the Foundations of Cryptography. Springer, 347\u2013450."},{"issue":"2","key":"e_1_3_2_55_2","doi-asserted-by":"crossref","first-page":"230","DOI":"10.2478\/popets-2020-0025","article-title":"Differentially private SQL with bounded user contribution","volume":"2020","author":"Wilson Royce J.","year":"2020","unstructured":"Royce J. Wilson, Celia Yuxin Zhang, William Lam, Damien Desfontaines, Daniel Simmons-Marengo, and Bryant Gipson. 2020. Differentially private SQL with bounded user contribution. Proceedings on Privacy Enhancing Technologies 2020, 2 (2020), 230\u2013250.","journal-title":"Proceedings on Privacy Enhancing Technologies"},{"issue":"8","key":"e_1_3_2_56_2","doi-asserted-by":"crossref","first-page":"1200","DOI":"10.1109\/TKDE.2010.247","article-title":"Differential privacy via wavelet transforms","volume":"23","author":"Xiao Xiaokui","year":"2010","unstructured":"Xiaokui Xiao, Guozhang Wang, and Johannes Gehrke. 2010. Differential privacy via wavelet transforms. IEEE Transactions on Knowledge and Data Engineering 23, 8 (2010), 1200\u20131214.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_3_2_57_2","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Yu Jianzhe","year":"2024","unstructured":"Jianzhe Yu, Wei Dong, Juanru Fang, Dajun Sun, and Ke Yi. 2024. DOP-SQL: A general-purpose, high-utility, and extensible private SQL system. In Proceedings of the International Conference on Very Large Data Bases."},{"key":"e_1_3_2_58_2","doi-asserted-by":"crossref","first-page":"731","DOI":"10.1145\/2723372.2737785","volume-title":"Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data","author":"Zhang Jun","year":"2015","unstructured":"Jun Zhang, Graham Cormode, Cecilia M. Procopiuc, Divesh Srivastava, and Xiaokui Xiao. 2015. Private release of graph statistics using ladder functions. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. 731\u2013745."},{"key":"e_1_3_2_59_2","first-page":"587","volume-title":"Proceedings of the 2014 SIAM International Conference on Data Mining","author":"Zhang Xiaojian","year":"2014","unstructured":"Xiaojian Zhang, Rui Chen, Jianliang Xu, Xiaofeng Meng, and Yingtao Xie. 2014. Towards accurate histogram publication under differential privacy. In Proceedings of the 2014 SIAM International Conference on Data Mining. 587\u2013595."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3697831","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3697831","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:30Z","timestamp":1750295850000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3697831"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,8]]},"references-count":58,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1145\/3697831"],"URL":"https:\/\/doi.org\/10.1145\/3697831","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,8]]},"assertion":[{"value":"2023-03-24","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-09","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}