PrivTree
Authors:
Open Access
- 14 June 2016
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 155-170
Abstract
Given a set D of tuples defined on a domain Omega, we study differentially private algorithms for constructing a histogram over Omega to approximate the tuple distribution in D. Existing solutions for the problem mostly adopt a hierarchical decomposition approach, which recursively splits Omega into sub-domains and computes a noisy tuple count for each sub-domain, until all noisy counts are below a certain threshold. This approach, however, requires that we (i) impose a limit h on the recursion depth in the splitting of Omega and (ii) set the noise in each count to be proportional to h. The choice of h is a serious dilemma: a small h makes the resulting histogram too coarse-grained, while a large h leads to excessive noise in the tuple counts used in deciding whether sub-domains should be split. Furthermore, h cannot be directly tuned based on D; otherwise, the choice of h itself reveals private information and violates differential privacy. To remedy the deficiency of existing solutions, we present PrivTree, a histogram construction algorithm that adopts hierarchical decomposition but completely eliminates the dependency on a pre-defined h. The core of PrivTree is a novel mechanism that (i) exploits a new analysis on the Laplace distribution and (ii) enables us to use only a constant amount of noise in deciding whether a sub-domain should be split, without worrying about the recursion depth of splitting. We demonstrate the application of PrivTree in modelling spatial data, and show that it can be extended to handle sequence data (where the decision in sub-domain splitting is not based on tuple counts but a more sophisticated measure). Our experiments on a variety of real datasets show that PrivTree considerably outperforms the states of the art in terms of data utility.Keywords
Funding Information
- Ministry of Education - Singapore (ARC19/14)
This publication has 44 references indexed in Scilit:
- Understanding hierarchical methods for differentially private histogramsProceedings of the VLDB Endowment, 2013
- Low-rank mechanismProceedings of the VLDB Endowment, 2012
- PrivBasisProceedings of the VLDB Endowment, 2012
- An adaptive mechanism for accurate query answering under differential privacyProceedings of the VLDB Endowment, 2012
- Boosting the accuracy of differentially private histograms through consistencyProceedings of the VLDB Endowment, 2010
- Differentially Private Data Release through Multidimensional PartitioningLecture Notes in Computer Science, 2010
- Differential Privacy2006
- Calibrating Noise to Sensitivity in Private Data Analysis2006
- The power of amnesia: Learning probabilistic automata with variable memory lengthMachine Learning, 1997
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975