Differentially Private Publishing of High-dimensional Data Using Sensitivity Control

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.