Query optimization for differentially private data management systems
Authors:
- 1 April 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1093-1104
Abstract
Differential privacy (DP) enables publishing statistical query results over sensitive data, with rigorous privacy guarantees, and very conservative assumptions about the adversary's background knowledge. This paper focuses on the interactive DP framework, which processes incoming queries on the fly, each of which consumes a portion of the user-specified privacy budget. Existing systems process each query independently, which often leads to considerable privacy budget waste. Motivated by this, we propose Pioneer, a query optimizer for an interactive, DP-compliant DBMS. For each new query, Pioneer creates an execution plan that combines past query results and new results from the underlying data. When a query has multiple semantically equivalent plans, Pioneer automatically selects one with minimal privacy budget consumption. Extensive experiments confirm that Pioneer achieves significant savings of the privacy budget, and can answer many more queries than existing systems for a fixed total budget, with comparable result accuracy.Keywords
This publication has 25 references indexed in Scilit:
- A rigorous and customizable framework for privacy2012
- GUPT2012
- An adaptive mechanism for accurate query answering under differential privacyProceedings of the VLDB Endowment, 2012
- Compressive mechanism2011
- No free lunch in data privacy2011
- Personalized social recommendationsProceedings of the VLDB Endowment, 2011
- Differentially-private network trace analysis2010
- Optimizing linear counting queries under differential privacy2010
- Privacy integrated queries2009
- Privacy: Theory meets Practice on the Map2008