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

Private Spatial Decomposition with Adaptive Grid

基于网格与差分隐私保护的空间数据分割得到了研究者的广泛关注,空间数据的大小、数据的偏斜性以及拉普拉斯噪音的多少直接制约着空间分割的精度.针对现有基于网格分割方法难以有效兼顾大规模空间数据、数据偏斜性与噪音量的不足,提出了一种基于伯努利随机抽样技术的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.