PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions
PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions
复制标题
DOI：
10.1145/2882903.2882928
复制
发表时间：
2016-01
期刊：
影响因子：
--
通讯作者：
Jun Zhang;Xiaokui Xiao;Xing Xie
中科院分区：
文献类型：
--
作者：
Jun Zhang;Xiaokui Xiao;Xing Xie
给定在域Ω上定义的元组集合D，我们研究用于在Ω上构建直方图以近似D中元组分布的差分隐私算法。该问题的现有解决方案大多采用层次分解方法，它递归地将Ω划分为子域，并为每个子域计算有噪声的元组计数，直到所有有噪声的计数都低于某个阈值。然而，这种方法要求我们（i）对Ω划分的递归深度施加限制h，以及（ii）将每个计数中的噪声设置为与h成正比。h的选择是一个严重的困境：较小的h会使得到的直方图粒度太粗，而较大的h会导致在用于决定是否应划分子域的元组计数中噪声过大。此外，h不能基于D直接调整；否则，h的选择本身会泄露隐私信息并违反差分隐私。为了弥补现有解决方案的不足，我们提出PrivTree，一种采用层次分解但完全消除对预定义h的依赖的直方图构建算法。PrivTree的核心是一种新颖的机制，它（i）利用对拉普拉斯分布的新分析，以及（ii）使我们能够在决定是否应划分子域时仅使用常量噪声，而无需担心划分的递归深度。我们展示了PrivTree在空间数据建模中的应用，并表明它可以扩展以处理序列数据（其中子域划分的决策不是基于元组计数，而是一种更复杂的度量）。我们在各种真实数据集上的实验表明，PrivTree在数据效用方面大大优于现有技术。
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.