基于四分树的差分隐私二维数据划分发布算法  

Differential privacy two-dimensional data partitioning publication algorithm based on quad-tree

作　　者：吴英杰[1] 卢清[1] 蔡剑平[1] 王晓东[1] 

机构地区：[1]福州大学数学与计算机科学学院,福建福州350108

出　　处：《华中科技大学学报（自然科学版）》2016年第3期99-104,共6页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(61300026);福建省自然科学基金资助项目(2014J01230)

摘　　要：为了提高差分隐私下二维数据区间计数查询的精度,提出一种基于四分树的差分隐私二维数据空间划分发布算法Quad-heu.首先构建与二维数据相对应的四分树,并对树节点添加拉普拉斯噪声;然后采用启发式判断策略,自底向上对四分树结构进行调整,以达到平衡查询噪声误差和均匀假设误差的目的;最后利用查询一致性约束对添加噪声后的四分树节点进行后置处理,以进一步提高查询精度.实验对算法Quad-heu所发布数据的区间计数查询精度及效率与同类算法进行比较分析,结果验证了其有效性.In order to boost the accuracy of range counting queries of the released two-dimensional space data under differential privacy,an algorithm Quad-heu based on quad-tree for differential privacy two-dimensional data publication by space partitioning was proposed.The basic idea of Quad-heu is to firstly construct a quad-tree with respect to the two-dimensional data and then add Laplace noise to tree nodes.After that,a bottom up heuristic approach for structural adjustment of the quad-tree was put forward,and the aim of which was to balance the noise error of queries and the error of uniform hypothesis.Finally,the accuracy of range counting queries was further reduced by post-processing the tree nodes′values through the consistency constraint of queries.Experimental analysis was designed by comparing Quad-heu and the traditional algorithms on the accuracy of range counting queries in the released data and the algorithm efficiency.Experimental results show that Quad-heu is effective and feasible.

关 键 词：隐私保护 四分树 差分隐私 空间划分 二维数据 启发式策略 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]