Differentially private data cubes: Optimizing noise sources and consistency

Bolin Ding, Marianne Winslett, Jiawei Han, Zhenhui Li

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Data cubes play an essential role in data analysis and decision support. In a data cube, data from a fact table is aggregated on subsets of the table's dimensions, forming a collection of smaller tables called cuboids. When the fact table includes sensitive data such as salary or diagnosis, publishing even a subset of its cuboids may compromise individuals' privacy. In this paper, we address this problem using differential privacy (DP), which provides provable privacy guarantees for individuals by adding noise to query answers. We choose an initial subset of cuboids to compute directly from the fact table, injecting DP noise as usual; and then compute the remaining cuboids from the initial set. Given a fixed privacy guarantee, we show that it is NP-hard to choose the initial set of cuboids so that the maximal noise over all published cuboids is minimized, or so that the number of cuboids with noise below a given threshold (precise cuboids) is maximized. We provide an efficient procedure with running time polynomial in the number of cuboids to select the initial set of cuboids, such that the maximal noise in all published cuboids will be within a factor (ln|L| + 1)2 of the optimal, where |L| is the number of cuboids to be published, or the number of precise cuboids will be within a factor (1 - 1/e) of the optimal. We also show how to enforce consistency in the published cuboids while simultaneously improving their utility (reducing error). In an empirical evaluation on real and synthetic data, we report the amounts of error of different publishing algorithms, and show that our approaches outperform baselines significantly.

Original languageEnglish (US)
Title of host publicationProceedings of SIGMOD 2011 and PODS 2011
Pages217-228
Number of pages12
DOIs
StatePublished - Jul 11 2011
Event2011 ACM SIGMOD and 30th PODS 2011 Conference - Athens, Greece
Duration: Jun 12 2011Jun 16 2011

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078

Other

Other2011 ACM SIGMOD and 30th PODS 2011 Conference
CountryGreece
CityAthens
Period6/12/116/16/11

Keywords

  • OLAP
  • data cube
  • differential privacy
  • private data analysis

ASJC Scopus subject areas

  • Software
  • Information Systems

Fingerprint Dive into the research topics of 'Differentially private data cubes: Optimizing noise sources and consistency'. Together they form a unique fingerprint.

Cite this