{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T16:06:22Z","timestamp":1786637182322,"version":"3.56.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T00:00:00Z","timestamp":1686096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2023,6,7]]},"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 (i.e., 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\/3604437.3604462","type":"journal-article","created":{"date-parts":[[2023,6,8]],"date-time":"2023-06-08T22:22:01Z","timestamp":1686262921000},"page":"115-123","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["R2T: Instance-optimal Truncation for Differentially Private Query Evaluation with Foreign Keys"],"prefix":"10.1145","volume":"52","author":[{"given":"Wei","family":"Dong","sequence":"first","affiliation":[{"name":"Hong Kong University of Science and Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Juanru","family":"Fang","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuchao","family":"Tao","sequence":"additional","affiliation":[{"name":"Duke University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ashwin","family":"Machanavajjhala","sequence":"additional","affiliation":[{"name":"Duke University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,6,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978318"},{"key":"e_1_2_1_2_1","first-page":"263","volume-title":"International Conference on Machine Learning","author":"Amin K.","year":"2019","unstructured":"K. Amin , A. Kulesza , A. Munoz , and S. Vassilvtiskii . Bounding user contributions: A bias-variance trade-off in differential privacy . In International Conference on Machine Learning , pages 263 -- 271 . PMLR, 2019 . K. Amin, A. Kulesza, A. Munoz, and S. Vassilvtiskii. Bounding user contributions: A bias-variance trade-off in differential privacy. In International Conference on Machine Learning, pages 263--271. PMLR, 2019."},{"key":"e_1_2_1_3_1","first-page":"33","author":"Asi H.","year":"2020","unstructured":"H. Asi and J. C. Duchi . Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms. Advances in Neural Information Processing Systems , 33 , 2020 . H. Asi and J. C. Duchi. 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_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422449"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465304"},{"key":"e_1_2_1_6_1","volume-title":"R2t: Instance-optimal truncation for differentially private query evaluation with foreign keys. url=https:\/\/www.cse.ust.hk\/ yike\/R2T.pdf","author":"Dong W.","year":"2022","unstructured":"W. Dong , J. Fang , K. Yi , Y. Tao , and A. Machanavajjhala . R2t: Instance-optimal truncation for differentially private query evaluation with foreign keys. url=https:\/\/www.cse.ust.hk\/ yike\/R2T.pdf , 2022 . W. Dong, J. Fang, K. Yi, Y. Tao, and A. Machanavajjhala. R2t: Instance-optimal truncation for differentially private query evaluation with foreign keys. url=https:\/\/www.cse.ust.hk\/ yike\/R2T.pdf, 2022."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452813"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524143"},{"key":"e_1_2_1_9_1","volume-title":"The algorithmic foundations of differential privacy. Foundations and Trends\u00ae in Theoretical Computer Science, 9(3--4):211--407","author":"Dwork C.","year":"2014","unstructured":"C. Dwork and A. Roth . The algorithmic foundations of differential privacy. Foundations and Trends\u00ae in Theoretical Computer Science, 9(3--4):211--407 , 2014 . C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Foundations and Trends\u00ae in Theoretical Computer Science, 9(3--4):211--407, 2014."},{"key":"e_1_2_1_10_1","volume-title":"NeurIPS","author":"Huang Z.","year":"2021","unstructured":"Z. Huang , Y. Liang , and K. Yi . Instance-optimal mean estimation under differential privacy . In NeurIPS , 2021 . Z. Huang, Y. Liang, and K. Yi. Instance-optimal mean estimation under differential privacy. In NeurIPS, 2021."},{"issue":"5","key":"e_1_2_1_11_1","first-page":"526","volume":"11","author":"Johnson N.","year":"2018","unstructured":"N. Johnson , J. P. Near , and D. Song . Towards practical differential privacy for sql queries. Proceedings of the VLDB Endowment , 11 ( 5 ): 526 -- 539 , 2018 . N. Johnson, J. P. Near, and D. Song. Towards practical differential privacy for sql queries. Proceedings of the VLDB Endowment, 11(5):526--539, 2018.","journal-title":"Towards practical differential privacy for sql queries. Proceedings of the VLDB Endowment"},{"key":"e_1_2_1_12_1","volume-title":"9th Innovations in Theoretical Computer Science Conference (ITCS 2018","author":"Karwa V.","year":"2018","unstructured":"V. Karwa and S. Vadhan . Finite sample differentially private confidence intervals . In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik , 2018 . V. Karwa and S. Vadhan. Finite sample differentially private confidence intervals. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_26"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342274"},{"key":"e_1_2_1_15_1","first-page":"49","volume-title":"Snap datasets: Stanford large network dataset collection","author":"Leskovec J.","year":"2014","unstructured":"J. Leskovec and A. Krevl . Snap datasets: Stanford large network dataset collection ( 2014 ). URL http:\/\/snap. stanford. edu\/data, page 49 , 2016. J. Leskovec and A. Krevl. Snap datasets: Stanford large network dataset collection (2014). URL http:\/\/snap. stanford. edu\/data, page 49, 2016."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250803"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389762"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57048-8_7"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3604437.3604462","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3604437.3604462","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:19Z","timestamp":1750178839000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3604437.3604462"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,7]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,6,7]]}},"alternative-id":["10.1145\/3604437.3604462"],"URL":"https:\/\/doi.org\/10.1145\/3604437.3604462","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2023,6,7]]},"assertion":[{"value":"2023-06-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}