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 proceedingpeer-review

71 Citations (Scopus)


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 (SIAM)
Number of pages9
ISBN (Electronic)9781510811515
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


Conference14th SIAM International Conference on Data Mining, SDM 2014
Country/TerritoryUnited States
Internet address

Scopus Subject Areas

  • Computer Science Applications
  • Software


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

Cite this