{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T05:11:31Z","timestamp":1755839491006},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:p>Most differentially private mechanisms are designed for the use of a single analyst. In reality, however, there are often multiple stakeholders with different and possibly conflicting priorities that must share the same privacy loss budget. This motivates the problem of equitable budget-sharing for multi-analyst differential privacy. Our previous work defined desiderata that any mechanism in this space should satisfy and introduced methods for budget-sharing in the offline case where queries are known in advance.<\/jats:p>\n          <jats:p>We extend our previous work on multi-analyst differentially private query answering to the case of online query answering, where queries come in one at a time and must be answered without knowledge of the following queries. We demonstrate that the unknown ordering of queries in the online case results in a fundamental limit in the number of queries that can be answered while satisfying the desiderata. In response, we develop two mechanisms, one which satisfies the desiderata in all cases but is subject to the fundamental limitations, and another that randomizes the input order ensuring that existing online query answering mechanisms can satisfy the desiderata.<\/jats:p>","DOI":"10.14778\/3574245.3574265","type":"journal-article","created":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T23:14:12Z","timestamp":1677021252000},"page":"816-828","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Multi-Analyst Differential Privacy for Online Query Answering"],"prefix":"10.14778","volume":"16","author":[{"given":"David","family":"Pujol","sequence":"first","affiliation":[{"name":"Duke University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Albert","family":"Sun","sequence":"additional","affiliation":[{"name":"Duke University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Brandon","family":"Fain","sequence":"additional","affiliation":[{"name":"Duke University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ashwin","family":"Machanavajjhala","sequence":"additional","affiliation":[{"name":"Duke University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,2,21]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Ullman","author":"Bun Mark","year":"2016","unstructured":"Mark Bun , Thomas Steinke , and Jonathan R . Ullman . 2016 . Make Up Your Mind: The Price of Online Queries in Differential Privacy. CoRR abs\/1604.04618 (2016). arXiv:1604.04618 http:\/\/arxiv.org\/abs\/1604.04618 Mark Bun, Thomas Steinke, and Jonathan R. Ullman. 2016. Make Up Your Mind: The Price of Online Queries in Differential Privacy. CoRR abs\/1604.04618 (2016). arXiv:1604.04618 http:\/\/arxiv.org\/abs\/1604.04618"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Bolin Ding and Marianne Winslett. 2011. Differentially Private Data Cubes : Optimizing Noise Sources and Consistency. (2011).  Bolin Ding and Marianne Winslett. 2011. Differentially Private Data Cubes : Optimizing Noise Sources and Consistency. (2011).","DOI":"10.1145\/1989323.1989347"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773173"},{"key":"e_1_2_1_4_1","unstructured":"Cynthia Dwork. 2006. Differential Privacy. In Automata Languages and Programming Michele Bugliesi Bart Preneel Vladimiro Sassone and Ingo Wegener (Eds.). Springer Berlin Heidelberg.  Cynthia Dwork. 2006. Differential Privacy. In Automata Languages and Programming Michele Bugliesi Bart Preneel Vladimiro Sassone and Ingo Wegener (Eds.). Springer Berlin Heidelberg."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Cynthia Dwork and Aaron Roth. 2014. The Algorithmic Foundations of Differential Privacy. Found. Trends Theor. Comput. Sci. (2014).  Cynthia Dwork and Aaron Roth. 2014. The Algorithmic Foundations of Differential Privacy. Found. Trends Theor. Comput. Sci. (2014).","DOI":"10.1561\/9781601988195"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1347082.1347189"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1347082.1347189"},{"key":"e_1_2_1_9_1","volume-title":"CoRR abs\/2002.12159","author":"Gupta Anupam","year":"2020","unstructured":"Anupam Gupta and Sahil Singla . 2020. Random-Order Models . CoRR abs\/2002.12159 ( 2020 ). arXiv:2002.12159 https:\/\/arxiv.org\/abs\/2002.12159 Anupam Gupta and Sahil Singla. 2020. Random-Order Models. CoRR abs\/2002.12159 (2020). arXiv:2002.12159 https:\/\/arxiv.org\/abs\/2002.12159"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035940"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.85"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Moritz Hardt and Kunal Talwar. 2009. On the Geometry of Differential Privacy. arXiv:0907.3754 [cs.CC]  Moritz Hardt and Kunal Talwar. 2009. On the Geometry of Differential Privacy. arXiv:0907.3754 [cs.CC]","DOI":"10.1145\/1806689.1806786"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920970"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807104"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2448496.2448529"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497436"},{"key":"e_1_2_1_17_1","unstructured":"John Abowd Daniel Kifer Brett Moran Robert Ashmead Philip Leclerc Wiliam Sexton Simson Garfinkel Ashwin Machanavajjhala. [n.d.]. Census TopDown: Differentially Private Data Incremental Schemas and Consistency with Public Knowledge. ([n. d.]). https:\/\/columbia.github.io\/private-systems-class\/papers\/Abowd2019Census.pdf  John Abowd Daniel Kifer Brett Moran Robert Ashmead Philip Leclerc Wiliam Sexton Simson Garfinkel Ashwin Machanavajjhala. [n.d.]. Census TopDown: Differentially Private Data Incremental Schemas and Consistency with Public Knowledge. ([n. d.]). https:\/\/columbia.github.io\/private-systems-class\/papers\/Abowd2019Census.pdf"},{"key":"e_1_2_1_18_1","volume-title":"Optimizing Error of High-dimensional Statistical Queries Under Differential Privacy. PVLDB 11, 10","author":"McKenna Ryan","year":"2018","unstructured":"Ryan McKenna , Gerome Miklau , Michael Hay , and Ashwin Machanavajjhala . 2018. Optimizing Error of High-dimensional Statistical Queries Under Differential Privacy. PVLDB 11, 10 ( 2018 ). Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavajjhala. 2018. Optimizing Error of High-dimensional Statistical Queries Under Differential Privacy. PVLDB 11, 10 (2018)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.2307\/2308930"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3467861.3467870"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556576"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.37236\/3348"},{"key":"e_1_2_1_23_1","volume-title":"AMIA Joint Summits on Translational Science proceedings. AMIA Joint Summits on Translational Science (Mar","author":"Vaidya Jaideep","year":"2013","unstructured":"Jaideep Vaidya , Basit Shafiq , Xiaoqian Jiang , and Lucila Ohno-Machado . 2013 . Identifying inference attacks against healthcare data repositories . AMIA Joint Summits on Translational Science proceedings. AMIA Joint Summits on Translational Science (Mar 2013). https:\/\/www.ncbi.nlm.nih.gov\/pmc\/articles\/PMC3845790\/ Jaideep Vaidya, Basit Shafiq, Xiaoqian Jiang, and Lucila Ohno-Machado. 2013. Identifying inference attacks against healthcare data repositories. AMIA Joint Summits on Translational Science proceedings. AMIA Joint Summits on Translational Science (Mar 2013). https:\/\/www.ncbi.nlm.nih.gov\/pmc\/articles\/PMC3845790\/"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973440.68"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3574245.3574265","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T23:14:52Z","timestamp":1677021292000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3574245.3574265"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["10.14778\/3574245.3574265"],"URL":"https:\/\/doi.org\/10.14778\/3574245.3574265","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,12]]},"assertion":[{"value":"2023-02-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}