Towards accurate Histogram publication under differential privacy

Xiaojian Zhang, Rui Ghent, Jianliang XU, Xiaofeng Meng, Yingtao Xie

Research output: Chapter in book/report/conference proceedingConference contributionpeer-review

47 Citations (Scopus)

Abstract

Histograms arc the workhorse of data mining and analysis. This paper considers the problem of publishing histograms under differential privacy, one of the strongest privacy models. Existing differentially private histogram publication schemes have shown that clustering (or grouping) is a promising idea to improve the accuracy of sanitized histograms. However, none of them fully exploits the benefit of clustering. In this paper, we introduce a new clustering framework. It features a sophisticated evaluation of the trade-off between the approximation error due to clustering and the Laplace error due to Laplace noise injected, which is normally overlooked in prior work. In particular, we propose three clustering strategies with different orders of run-time complexitics. We prove the superiority of our approach by theoretical utility comparisons with the competitors. Our extensive experiments over various standard real-life and synthetic datasets confirm that our technique consistently outperforms existing competitors.

Original languageEnglish
Title of host publicationSIAM International Conference on Data Mining 2014, SDM 2014
EditorsPang Ning-Tan, Arindam Banerjee, Srinivasan Parthasarathy, Zoran Obradovic, Chandrika Kamath, Mohammed Zaki
PublisherSociety for Industrial and Applied Mathematics Publications
Pages587-595
Number of pages9
ISBN (Electronic)9781510811515
DOIs
Publication statusPublished - 2014
Event14th SIAM International Conference on Data Mining, SDM 2014 - Philadelphia, United States
Duration: 24 Apr 201426 Apr 2014

Publication series

NameSIAM International Conference on Data Mining 2014, SDM 2014
Volume2

Conference

Conference14th SIAM International Conference on Data Mining, SDM 2014
Country/TerritoryUnited States
CityPhiladelphia
Period24/04/1426/04/14

Scopus Subject Areas

  • Computer Science Applications
  • Software

Fingerprint

Dive into the research topics of 'Towards accurate Histogram publication under differential privacy'. Together they form a unique fingerprint.

Cite this