att_abstract={{A central problem in releasing information is to do so accurately while providing a privacy guarantee on the output. Recently, there has been much work which guarantees differential privacy on the output, and aims to maximize the utility within this guarantee, for the class of {em linear queries}, which include basic counting queries, data cubes, and contingency tables. Much work follows a common template: pick a ``strategy'' set of linear queries to apply to the data, then use the noisy answers to these queries to reconstruct the queries of interest. This entails either picking a strategy set that is hoped to be good for the queries, or by performing an exhaustive search over the space of all possible strategies.

In this paper, we propose a new approach that balances accuracy and
efficiency:  we show how to optimize the accuracy of a given strategy by
answering some strategy queries more accurately than others, based on the target queries. This leads to an efficient optimal noise allocation for many popular strategies, including wavelets, hierarchies, Fourier coefficients and more.
For the important case of marginal queries (equivalently, subsets of the data cube), we show that this strictly improves on previous methods, both analytically and empirically. Our results also extend to ensuring that the returned query answers are consistent with an (unknown) data set at minimal extra cost in
terms of time and noise.
	att_authors={gc2602, cp2838, ds8961},
	att_copyright_notice={{This version of the work is reprinted here with permission of IEEE for your personal use. Not for redistribution. The definitive version was published in  2012 {{, 2013-04-08}}
	author={Graham Cormode and Cecilia Procopiuc and Divesh Srivastava and Grigory Yaroslavtsev},
	institution={{IEEE International Conference on Data Engineering}},
	title={{Accurate and Efficient Private Release of Datacubes and Contingency Tables}},