{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:04:04Z","timestamp":1750309444783,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:00:00Z","timestamp":1740096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:p>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 and 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 (that is, satisfy DP), but they do not offer nontrivial utility guarantees or are very complicated and costly. In this paper, we propose the first DP mechanism for answering arbitrary SPJA queries in a database with foreign-key constraints. Meanwhile, it achieves a fairly strong notion of optimality, which can be considered as a small and natural relaxation of instance optimality. Finally, our mechanism is simple enough that it can be easily implemented on top of any RDBMS and an LP solver. Experimental results show that it offers order-of-magnitude improvements in terms of utility over existing techniques, even those specifically designed for graph pattern counting.<\/jats:p>","DOI":"10.1145\/3708494","type":"journal-article","created":{"date-parts":[[2025,2,19]],"date-time":"2025-02-19T21:05:36Z","timestamp":1739999136000},"page":"93-101","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["R2T: Instance-optimal Truncation for Differentially Private Query Evaluation with Foreign Keys"],"prefix":"10.1145","volume":"68","author":[{"given":"Wei","family":"Dong","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juanru","family":"Fang","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuchao","family":"Tao","sequence":"additional","affiliation":[{"name":"Duke University, Durham, North Carolina, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ashwin","family":"Machanavajjhala","sequence":"additional","affiliation":[{"name":"Duke University, Durham, North Carolina, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,2,21]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"crossref","unstructured":"Abadi M. et al. Deep learning with differential privacy. In Proceedings of the 2016 ACM Conf. on Computer and Communications Security (2016) 308\u2013318.","DOI":"10.1145\/2976749.2978318"},{"key":"e_1_3_1_3_2","first-page":"263","volume-title":"Intern. Conf. on Machine Learning","author":"Amin K.","year":"2019","unstructured":"Amin, K., Kulesza, A., Munoz, A., and Vassilvtiskii, S. Bounding user contributions: A bias-variance trade-off in differential privacy. In Intern. Conf. on Machine Learning. PMLR (2019), 263\u2013271."},{"key":"e_1_3_1_4_2","article-title":"Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms","volume":"33","author":"Asi H.","year":"2020","unstructured":"Asi, H. and Duchi, J.C. Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms. Advances in Neural Information Processing Systems 33 (2020).","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_1_5_2","doi-asserted-by":"crossref","unstructured":"Blocki J. Blum A. Datta A. and Sheffet O. Differentially private data analysis of social networks via restricted sensitivity. In Proceedings of the 4th Conf. on Innovations in Theoretical Computer Science (2013) 87\u201396.","DOI":"10.1145\/2422436.2422449"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3589287"},{"key":"e_1_3_1_7_2","doi-asserted-by":"crossref","unstructured":"Chen S. and Zhou S. Recursive mechanism: towards node differential privacy and unrestricted joins. In Proceedings of the 2013 ACM SIGMOD Intern. Conf. on Management of Data (2013) 653\u2013664.","DOI":"10.1145\/2463676.2465304"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3654931"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3697831"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP46215.2023.10179466"},{"issue":"2","key":"e_1_3_1_11_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 W.","year":"2023","unstructured":"Dong, W., Sun, D., and Yi, K. 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_1_12_2","doi-asserted-by":"crossref","unstructured":"Dong W. and Yi K. Residual sensitivity for differentially private multi-way joins. In Proc. ACM SIGMOD Intern. Conf. on Management of Data (2021).","DOI":"10.1145\/3448016.3452813"},{"key":"e_1_3_1_13_2","doi-asserted-by":"crossref","unstructured":"Dong W. and Yi K. A nearly instance-optimal differentially private mechanism for conjunctive queries. In Proc. ACM Symp. on Principles of Database Systems (2022).","DOI":"10.1145\/3517804.3524143"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3631504.3631506"},{"key":"e_1_3_1_15_2","doi-asserted-by":"crossref","unstructured":"Dong W. and Yi K. Universal private estimators. In Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symp. on Principles of Database Systems (2023) 195\u2013206.","DOI":"10.1145\/3584372.3588669"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000042"},{"key":"e_1_3_1_17_2","doi-asserted-by":"crossref","unstructured":"Fang J. Dong W. and Yi K. Shifted inverse: A general mechanism for monotonic functions under user differential privacy (2022).","DOI":"10.1145\/3548606.3560567"},{"key":"e_1_3_1_18_2","unstructured":"Huang Z. Liang Y. and Yi K. Instance-optimal mean estimation under differential privacy. In NeurIPS (2021)."},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3177733"},{"key":"e_1_3_1_20_2","volume-title":"Proceedings of the\u00a09th Innovations in Theoretical Computer Science Conf","author":"Karwa V.","year":"2018","unstructured":"Karwa, V. and Vadhan, S. Finite sample differentially private confidence intervals. In Proceedings of the\u00a09th Innovations in Theoretical Computer Science Conf. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018."},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_26"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342274"},{"key":"e_1_3_1_23_2","unstructured":"Leskovec J. and Krevl A. Snap datasets: Stanford large network dataset collection (2014) 49; https:\/\/tinyurl.com\/22cypyg3"},{"key":"e_1_3_1_24_2","doi-asserted-by":"crossref","unstructured":"Nissim K. Raskhodnikova S. and Smith A. Smooth sensitivity and sampling in private data analysis. In Proceedings of the 39th Ann. ACM Symp. on Theory of Computing (2007) 75\u201384.","DOI":"10.1145\/1250790.1250803"},{"key":"e_1_3_1_25_2","doi-asserted-by":"crossref","unstructured":"Tao Y. He X. Machanavajjhala A. and Roy S. Computing local sensitivities of counting queries with joins. In Proceedings of the 2020 ACM SIGMOD Intern. Conf. on Management of Data (2020) 479\u2013494.","DOI":"10.1145\/3318464.3389762"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57048-8_7"},{"key":"e_1_3_1_27_2","doi-asserted-by":"crossref","unstructured":"Yu J. et al. Dop-sql: A general-purpose high-utility and extensible private sql system. In Proc. Intern. Conf. on Very Large Data Bases (2024).","DOI":"10.14778\/3685800.3685881"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3708494","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3708494","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:09:54Z","timestamp":1750295394000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3708494"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,21]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["10.1145\/3708494"],"URL":"https:\/\/doi.org\/10.1145\/3708494","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"type":"print","value":"0001-0782"},{"type":"electronic","value":"1557-7317"}],"subject":[],"published":{"date-parts":[[2025,2,21]]},"assertion":[{"value":"2025-02-21","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}