You can manage bookmarks using lists, please log in to your user account for this.
Media type:
E-Article
Title:
Better than Composition: How to Answer Multiple Relational Queries under Differential Privacy
Contributor:
Dong, Wei;
Sun, Dajun;
Yi, Ke
imprint:
Association for Computing Machinery (ACM), 2023
Published in:Proceedings of the ACM on Management of Data
Language:
English
DOI:
10.1145/3589268
ISSN:
2836-6573
Origination:
Footnote:
Description:
<jats:p>Answering relational queries under differential privacy has attracted a lot of attention in recent years due to growing concerns on personal privacy, and instance-optimal mechanisms have been developed for a single query. However, most real-world data analytical tasks require multiple queries to be answered under a total privacy budget. The standard solution to extend the single-query mechanism to multiple queries is via privacy composition. However, we observe that this may yield an error bound that could be a d0.5-factor worse from the optimal, where d is the number of queries. In this paper, we present a different, more holistic approach that closes this gap. In addition to theoretical optimality, our new mechanism also significantly outperforms privacy composition in practice, especially on more skewed data and large d.</jats:p>