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

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

项目编号： No.61300026

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 自动化技术、计算机技术

项目作者： 吴英杰

作者单位： 福州大学

项目金额： 23万元

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

中文关键词： 差分隐私；直方图发布；线性无偏估计；任意树结构；流数据发布

英文摘要： 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 privac

英文关键词： Differential privacy；histogram publication；linear unbiased estimation；any tree structure；streaming data publication