Differentially Private Publishing of High-dimensional Data Using Sensitivity Control
Authors:
Open Access
- 14 April 2015
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 451-462
Abstract
In this paper, we present DPSense, an approach to publish statistical information from datasets under differential privacy via sensitivity control. More specifically, we consider the problem of publishing column counts for high-dimensional datasets, such as query logs or the Netflix dataset. The key challenge is that as the sensitivity is high, high-magnitude noises need to be added to satisfy differential privacy. We explore how to effectively performs sensitivity control, i.e., limiting the contribution of each tuple in the dataset. We introduce a novel low-sensitivity quality function that enables one to effectively choose a contribution limit while satisfying differential privacy. Based on DPSense, we further propose an extension to correct the under-estimation bias, which we call DPSense-S. Experimental results show that our proposed approaches advance the state of the art for publishing noisy column counts and for finding the columns with the highest counts. Finally, we give the analysis and discussion for the stability of DPSense and DPSense-S, which benefits from the high correlation between quality function and error, as well as other insights of DPSense, DPSense-S, and existing approaches.Keywords
Funding Information
- United States National Science Foundation (1116991)
- National Science Foundation (1116991)
This publication has 24 references indexed in Scilit:
- Calibrating data to sensitivity in private data analysisProceedings of the VLDB Endowment, 2014
- Practical differential privacy via grouping and smoothingProceedings of the VLDB Endowment, 2013
- Analyzing Graphs with Node Differential Privacy2013
- PrivBasisProceedings of the VLDB Endowment, 2012
- Faster Algorithms for Privately Releasing Marginals2012
- Boosting the accuracy of differentially private histograms through consistencyProceedings of the VLDB Endowment, 2010
- Discovering frequent patterns in sensitive data2010
- Differential Privacy2006
- Calibrating Noise to Sensitivity in Private Data Analysis2006
- Cumulated gain-based evaluation of IR techniquesACM Transactions on Information Systems, 2002