### 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 language | English (US) |
---|---|

Title of host publication | Proceedings of SIGMOD 2011 and PODS 2011 |

Pages | 217-228 |

Number of pages | 12 |

DOIs | |

State | Published - Jul 11 2011 |

Event | 2011 ACM SIGMOD and 30th PODS 2011 Conference - Athens, Greece Duration: Jun 12 2011 → Jun 16 2011 |

### Publication series

Name | Proceedings of the ACM SIGMOD International Conference on Management of Data |
---|---|

ISSN (Print) | 0730-8078 |

### Other

Other | 2011 ACM SIGMOD and 30th PODS 2011 Conference |
---|---|

Country | Greece |

City | Athens |

Period | 6/12/11 → 6/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

*Proceedings of SIGMOD 2011 and PODS 2011*(pp. 217-228). (Proceedings of the ACM SIGMOD International Conference on Management of Data). https://doi.org/10.1145/1989323.1989347