Integrating historical noisy answers for improving data utility under differential privacy

• Main Authors: Bhowmick, Sourav S., Chen, Shixi, Zhou, Shuigeng
• Other Authors: School of Computer Engineering
• Format: Conference or Workshop Item
• Language: English
• Published: 2013
• Online Access: https://hdl.handle.net/10356/84235; http://hdl.handle.net/10220/12280
• Institution: Nanyang Technological University

Differential privacy is a robust principle for privacy preserving data analysis tasks, and has been successfully applied to a variety of applications. However, the number of queries that can be answered is limited for preventing privacy disclosure. Once the privacy budget is exhausted, all succeeding queries must be rejected. Therefore, each of the historical query answers is valuable and it is important to exploit them together to learn more about the data. We propose to integrate all available linear query answers into a consistent form that embodies our knowledge learned from the noisy answers, obtaining more accurate answers to past queries and even new queries, improving the data utility. Two distinct approaches are developed for this purpose, one via principle component analysis, and another via maximum entropy method. The second approach also generates a synthetic database, which is useful for differentially private data publishing. One important goal of our work is to ensure that the running time of our approaches does not grow with the cardinality of the universe of a data tuple, so that high-dimensional data with very large domain can still be tackled efficiently.