基于自适应网格的隐私空间分割方法

来源：计算机研究与发展杂志2018年第6期北京时间：

作者：张啸剑,金凯忠,孟小峰,

摘要：基于网格与差分隐私保护的空间数据分割得到了研究者的广泛关注，空间数据的大小、数据的偏斜性以及拉普拉斯噪音的多少直接制约着空间分割的精度.针对现有基于网格分割方法难以有效兼顾大规模空间数据、数据偏斜性与噪音量的不足，提出了一种基于伯努利随机抽样技术的3层自适应网格分割(sampling-basedthree-layeradaptivegriddecomposition,STAG)方法，该方法利用满足差分隐私的抽样技术抽取空间数据点作为分割对象.根据查询粒度的不同，首先在中间层利用指数机制与高通滤波过滤掉小于阈值的网格单元，然后利用Down-Split方法继续细分大于阈值的网格单元.对于那些小于阈值且连接的单元格，利用Up-Merge操作对这些单元进行最优化重组，形成粗粒度的网格单元.STAG与UG(uniformgrid)，AG(adaptivegrid)，Kd-Stand(kd-tree-basedstandardmethod)，Kd-Hybrid(kd-tree-basedhybridmethod)在真实的大规模空间数据集上实验结果表明：其分割精度以及响应范围查询效果优于同类算法.

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