This work 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 and consequently fast exhaustion of the total budget. 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.
- S. Peng, Y. Yang, Zhang, Z., M. Winslett and Y. Yu. Query Optimization for Differentially Private Data Management Systems. ICDE, 2013.