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)，Kd-Hybrid(kd-tree-based hybrid method)在真实的大规模空间数据集上实验结果表明：其分割精度以及响应范围查询效果优于同类算法.Abstract: 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 Up-Merge 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.
-
-
期刊类型引用(4)
1. 刘华玲，梁华璧，王希睿. 中国个人信息保护应用与技术进展研究——基于科学知识图谱视角. 情报工程. 2024(01): 42-58 . 
百度学术
2. 尹春勇，贾续康. 基于策略图的三维位置隐私发布算法研究. 信息网络安全. 2024(04): 602-613 . 百度学术
3. 晏燕，丛一鸣，Adnan Mahmood，盛权政. 基于深度学习的位置大数据统计发布与隐私保护方法. 通信学报. 2022(01): 203-216 . 百度学术
4. 王明月，张兴，李万杰，张青云，李晓会. 面向数据发布的隐私保护技术研究综述. 小型微型计算机系统. 2020(12): 2657-2667 . 百度学术
其他类型引用(15)
计量
- 文章访问数: 1500
- HTML全文浏览量: 3
- PDF下载量: 666
- 被引次数: 19
下载:
