文献类型：期刊文献

中文题名：基于自适应网格的隐私空间分割方法

英文题名：Private Spatial Decomposition with Adaptive Grid

作者：张啸剑[1];金凯忠[1];孟小峰[2]

第一作者：张啸剑

机构：[1]河南财经政法大学计算机与信息工程学院;[2]中国人民大学信息学院

第一机构：河南财经政法大学计算机与信息工程学院

年份：2018

卷号：55

期号：6

起止页码：1143-1156

中文期刊名：计算机研究与发展

外文期刊名：Journal of Computer Research and Development

收录：CSTPCD;;EI(收录号：20183805839781);Scopus;北大核心:【北大核心2017】；CSCD:【CSCD2017_2018】；

基金：国家自然科学基金项目(61502146;91746115;91646203;61572420);河南省自然科学基金面上项目(162300410006);河南省科技攻关项目(162102310411);河南省教育厅高等学校重点科研项目(16A520002);河南财经政法大学青年拔尖人才资助计划项目~~

语种：中文

中文关键词：差分隐私;自适应网格;隐私空间划分;伯努利随机抽样;约束推理

外文关键词：differential privacy;adaptive grid;private spatial decomposition;Bernoulli randomsampling;constrained inference

摘要：基于网格与差分隐私保护的空间数据分割得到了研究者的广泛关注,空间数据的大小、数据的偏斜性以及拉普拉斯噪音的多少直接制约着空间分割的精度.针对现有基于网格分割方法难以有效兼顾大规模空间数据、数据偏斜性与噪音量的不足,提出了一种基于伯努利随机抽样技术的3层自适应网格分割(sampling-based three-layer adaptive grid decomposition,STAG)方法,该方法利用满足差分隐私的抽样技术抽取空间数据点作为分割对象.根据查询粒度的不同,首先在中间层利用指数机制与高通滤波过滤掉小于阈值的网格单元,然后利用Down-Split方法继续细分大于阈值的网格单元.对于那些小于阈值且连接的单元格,利用Up-Merge操作对这些单元进行最优化重组,形成粗粒度的网格单元.STAG与UG(uniform grid),AG(adaptive grid),Kd-Stand(kd-tree-based standard method),KdHybrid(kd-tree-based hybrid method)在真实的大规模空间数据集上实验结果表明:其分割精度以及响应范围查询效果优于同类算法.
Grid-based differentially private spatial decomposition has attracted considerable research attention in recent years.The trade-off among the size of spatial data,data skew,and Laplace noise directly constrains the accuracy of decomposition.Most state-of-the-art methods based on grid cannot efficiently accommodate the three constraints.To address the above questions,this paper proposes a three-layer adaptive grid,called STAG,to decompose the spatial data with differential privacy.STAG employs Bernoulli random sampling method to retrieve the samples as decomposition data in the second level.According to the different query granularities in the second level,some cells whose counts are smaller than the given threshold will be filtered by exponential mechanism and high-pass filter techniques.For the cells whose counts are over the threshold,STAG uses Down-Split method to decompose them into fine-grained cells in the third level.For the filtered cells,STAG utilizes UpMerge method to group them into coarse-grained cells with optimal grouping skill in the first level.STAG method is compared with the existing methods such as UG,AG,Kd-Stand,and Kd-Hybrid on the large-scale real datasets. The experimental results show that the STAG outperforms its competitors,achieves the accurate decomposition and results of range query.