{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,24]],"date-time":"2025-11-24T07:16:18Z","timestamp":1763968578778},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,11]]},"abstract":"<jats:p>Whenever randomness is involved in query processing, confidence intervals are commonly returned to the user to indicate the statistical significance of the query answer. However, this problem has not been explicitly addressed under differential privacy, which must use randomness by definition. For some classical mechanisms whose noise distribution does not depend on the input, such as the Laplace and the Gaussian mechanism, deriving confidence intervals is easy. But the problem becomes nontrivial for queries whose global sensitivity is large or unbounded, for which these classical mechanisms cannot be applied. There are three main techniques in the literature for dealing with such queries: the exponential mechanism, the sparse vector technique, and the smooth sensitivity. In this paper, for each of the three techniques we design mechanisms to produce confidence intervals that are (1) differentially private; (2) correct, i.e., the interval contains the true query answer with the specified confidence level; and (3) have a utility guarantee matching that of the original mechanism, up to constant factors. Then we show how to apply our techniques to a variety of problems ranging from simple statistics (e.g., mean, median, maximum) to graph pattern counting and conjunctive queries.<\/jats:p>","DOI":"10.14778\/3632093.3632102","type":"journal-article","created":{"date-parts":[[2024,1,20]],"date-time":"2024-01-20T11:26:31Z","timestamp":1705749991000},"page":"373-385","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Confidence Intervals for Private Query Processing"],"prefix":"10.14778","volume":"17","author":[{"given":"Dajun","family":"Sun","sequence":"first","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Dong","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"}]}],"member":"320","published-online":{"date-parts":[[2024,1,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465355"},{"key":"e_1_2_1_2_1","volume-title":"Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms. Advances in neural information processing systems 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), 14106--14117."},{"key":"e_1_2_1_3_1","volume-title":"Near instance-optimality in differential privacy. arXiv preprint arXiv.2005.10630","author":"Asi Hilal","year":"2020","unstructured":"Hilal Asi and John C Duchi. 2020. Near instance-optimality in differential privacy. arXiv preprint arXiv.2005.10630 (2020)."},{"key":"e_1_2_1_4_1","volume-title":"Shiva Prasad Kasiviswanathan, and Kobbi Nissim","author":"Beimel Amos","year":"2014","unstructured":"Amos Beimel, Hai Brenner, Shiva Prasad Kasiviswanathan, and Kobbi Nissim. 2014. Bounds on the sample complexity for private learning and private data release. Machine learning 94 (2014), 401--437."},{"key":"e_1_2_1_5_1","first-page":"14475","article-title":"Coin-Press: Practical Private Mean and Covariance Estimation","volume":"33","author":"Biswas Sourav","year":"2020","unstructured":"Sourav Biswas, Yihe Dong, Gautam Kamath, and Jonathan Ullman. 2020. Coin-Press: Practical Private Mean and Covariance Estimation. In Advances in Neural Information Processing Systems, Vol. 33. 14475--14485.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.45"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53641-4_24"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056097"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.16"},{"key":"e_1_2_1_10_1","volume-title":"Unbiased statistical estimation and valid confidence intervals under differential privacy. arXiv preprint arXiv:2110.14465","author":"Covington Christian","year":"2021","unstructured":"Christian Covington, Xi He, James Honaker, and Gautam Kamath. 2021. Unbiased statistical estimation and valid confidence intervals under differential privacy. arXiv preprint arXiv:2110.14465 (2021)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517844"},{"key":"e_1_2_1_12_1","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--26.","journal-title":"Proceedings of the ACM on Management of Data"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452813"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524143"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3631504.3631506"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588669"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1093\/jssam\/smac021"},{"key":"e_1_2_1_18_1","volume-title":"Differentially private confidence intervals. arXiv preprint arXiv:2001.02285","author":"Du Wenxin","year":"2020","unstructured":"Wenxin Du, Canyon Foot, Monica Moniot, Andrew Bray, and Adam Groce. 2020. Differentially private confidence intervals. arXiv preprint arXiv:2001.02285 (2020)."},{"key":"e_1_2_1_19_1","unstructured":"Dheeru Dua and Casey Graff. 2017. UCI Machine Learning Repository. http:\/\/archive.ics.uci.edu\/ml"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536466"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536466"},{"key":"e_1_2_1_22_1","volume-title":"Theory of cryptography conference","author":"Dwork Cynthia","unstructured":"Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference. Springer, 265--284."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536467"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Cynthia Dwork Aaron Roth et al. 2014. The algorithmic foundations of differential privacy. Foundations and Trends\u00ae in Theoretical Computer Science 9 3--4 (2014) 211--407.","DOI":"10.1561\/0400000042"},{"key":"e_1_2_1_25_1","volume-title":"Concentrated differential privacy. arXiv preprint arXiv 1603.01887","author":"Dwork Cynthia","year":"2016","unstructured":"Cynthia Dwork and Guy N Rothblum. 2016. Concentrated differential privacy. arXiv preprint arXiv 1603.01887 (2016)."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of The 25th International Conference on Artificial Intelligence and Statistics. 1598--1618","author":"Ferrando Cecilia","year":"2022","unstructured":"Cecilia Ferrando, Shufan Wang, and Daniel Sheldon. 2022. Parametric Bootstrap for Differentially Private Confidence Intervals. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics. 1598--1618."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253291"},{"key":"e_1_2_1_28_1","volume-title":"Instance-optimal Mean Estimation Under Differential Privacy. Advances in Neural Information Processing Systems","author":"Huang Ziyue","year":"2021","unstructured":"Ziyue Huang, Yuting Liang, and Ke Yi. 2021. Instance-optimal Mean Estimation Under Differential Privacy. Advances in Neural Information Processing Systems (2021)."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3177733"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402749"},{"key":"e_1_2_1_31_1","unstructured":"Vishesh Karwa and Salil Vadhan. 2017. Finite Sample Differentially Private Confidence Intervals."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_26"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342274"},{"key":"e_1_2_1_34_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915235"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.66"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dss.2014.03.001"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250803"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732296.2732300"},{"key":"e_1_2_1_40_1","unstructured":"Dajun Sun Wei Dong and Ke Yi. 2023. Confidence Intervals for Private Query Processing. https:\/\/drive.google.com\/file\/d\/1nk5HqZQT5J4hFEwGx1TOZOs0KRSYd1gh\/view"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2737785"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3632093.3632102","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,20]],"date-time":"2024-01-20T11:31:43Z","timestamp":1705750303000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3632093.3632102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["10.14778\/3632093.3632102"],"URL":"https:\/\/doi.org\/10.14778\/3632093.3632102","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,11]]},"assertion":[{"value":"2024-01-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}