基于线性无偏估计面向任意树结构的差分隐私直方图发布

Differential privacy histogram publishing has become a hot topic in data privacy preserving research community. The aim of this project is to propose efficient differential privacy histogram release algorithms for any tree structure based on linear unbiased estimation, so as to boost the accuracy of range counting queries and improve the efficiency of histogram release algorithms. By statistical linear regression theory, the project will firstly build a differential privacy histogram release model based on linear unbiased estimation under the tree consistency constraint, and then present an efficient algorithm to solve weighted least squares. Secondly, the project will propose an efficient algorithm for computing the coverage propability of tree nodes in differential privacy interval tree under some specific probability distribution of range counting queries. After that, some effective differential privacy histogram release algorithms will be presented. For homoscedasticity, the accuracy of range counting queries can be boosted by heuristic tree reconstruction, and for heteroscedasticity, the accuracy of range counting queries can be boosted by reallocating the differential privacy parameters of tree nodes. The project is expected to further enrich and improve the theories and algorithms in differential privacy histogram publication and provide theoretical and technical support to related applications.

本项目以差分隐私直方图发布为基本背景，以提高区间计数查询精度和算法效率为基本目标，研究基于线性无偏估计面向任意树结构的差分隐私直方图发布算法。基于统计学中线性回归的相关理论，利用任意区间树的一致性约束建立基于线性无偏估计的差分隐私直方图发布模型，设计出加权最小二乘的高效算法；在区间计数查询满足特定概率分布下，利用概率论相关知识计算差分隐私区间树节点的覆盖概率，并据此设计出差分隐私直方图发布算法：在添加噪声同方差下，以有效降低区间计数查询噪声方差期望为目标，通过启发式树重构实现差分隐私直方图发布；在添加噪声异方差下，利用数学分析方法，建立区间计数查询误差的数学模型，以最小化区间计数查询噪声方差期望为目标，通过制定差分隐私区间树节点隐私参数的分配策略实现差分隐私直方图发布。本项目研究有望进一步丰富和完善差分隐私保护直方图发布的理论和算法，为基于差分隐私的相关应用提供理论和技术支持。

直方图发布是一种重要的差分隐私数据发布形式。项目针对面向任意区间树结构的差分隐私直方图发布、基于区间查询概率进行树重构的差分隐私直方图发布、异方差加噪下的差分隐私直方图发布、面向任意区间查询的差分隐私流数据自适应发布等科学问题进行了深入研究。项目取得了如下主要研究进展：(1)在区间树定义的基础上，提出可实现任意直方图向区间树映射的k-区间树结构；通过理论分析表明，对于任意区间树结构下的差分隐私直方图发布，仍然可在一致性约束下利用最优线性无偏估计进一步降低区间计数查询的误差；进而设计出面向任意区间树结构基于最优线性无偏估计的差分隐私直方图发布算法。(2)现有基于树形结构的差分隐私直方图发布方法均未考虑用户区间查询概率可能对整体区间查询精度的影响。通过研究分析发现，不同的用户区间查询概率将使差分隐私区间树中不同节点的覆盖概率不尽相同，从而导致整体区间查询误差的期望值因树结构不同而存在较大差别。为此，提出一种基于区间查询概率的差分隐私直方图发布算法。针对给定的用户区间查询概率，以最小化整体区间查询误差的期望值为目标进行差分隐私区间树的构造，并利用最优线性无偏估计对差分隐私区间树进行一致性调节，进一步提高区间查询的精度。（3）提出一种异方差加噪下面向任意区间树结构的差分隐私直方图发布算法。算法首先根据区间计数查询的分布，计算区间树中节点的覆盖概率，并据此分配隐私预算，实现异方差加噪；接着分析指出该异方差加噪策略适用于任意区间树结构，从理论上证明，在任意区间树结构下进行异方差加噪后，仍可在一致性约束下利用最优线性无偏估计进一步降低区间计数查询的误差。(4) 针对流数据任意区间计数查询问题，提出一个基于历史查询的差分隐私流数据自适应发布算法，结合流数据的特性，利用滑动窗口机制动态构建窗口内流数据对应的差分隐私区间树，计算树节点覆盖概率，并据此对树节点进行异方差加噪，最后根据历史查询规律自适应调整树节点的隐私预算与树结构参数。项目研究为基于差分隐私的相关应用提供理论和技术支持，并进一步丰富和完善差分隐私保护直方图发布的理论和算法。