基于本地差分隐私的空间范围查询方法

张啸剑; 付楠; 孟小峰

doi:10.7544/issn1000-1239.2020.20190360

基于本地差分隐私的空间范围查询方法

¹(河南财经政法大学计算机与信息工程学院郑州 450002)
²(中国人民大学信息学院北京 100872) (xjzhang82@ruc.edu.cn)

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

详细信息

中图分类号: TP392
计量
- 文章访问数: 1205
- HTML全文浏览量: 4
- PDF下载量: 407
出版历程
- 发布日期: 2020-03-31

Towards Spatial Range Queries Under Local Differential Privacy

¹(School of Computer & Information Engineering, Henan University of Economics and Law, Zhengzhou 450002)
²(School of Information, Renmin University of China, Beijing 100872)

Funds: This work was supported by the National Natural Science Foundation of China (61502146, 61572420, 91646203, 91746115), the Natural Science Foundation of Henan Province (162300410006), the Key Technologies Research and Development Program of Henan Province (162102310411), the Research Program of the Higher Education of Henan Educational Committee (16A520002), and the Young Talents Fund of Henan University of Economics and Law.

摘要

摘要: 基于本地差分隐私的用户数据收集与分析得到了研究者的广泛关注.用户数据的值域大小、编码机制以及扰动机制直接制约着空间范围查询的精度.针对现有编码机制与扰动机制难以有效响应空间范围查询的不足，提出了一种基于网格分割与四分树索引的空间范围查询响应方法GT-R(grid-based quadtree range query)，该方法利用网格对用户数据的值域进行均匀分割，产生大小均等的单元格区域.同时利用四分树结构对所有单元格区域进行索引.每个用户结合服务器共享的四分树副本，对所拥有的数据进行编码.借助于编码后的四分树进行层次随机采样，并利用优化随机应答机制对所采层次中的结点进行本地扰动处理.服务器利用每个用户的报告值重构四分树索引结构，并响应空间范围查询.GT-R与现有的编码机制与扰动机制在真实的大规模空间数据集上实验结果表明，其分割精度以及响应范围查询效果优于同类算法.
- 本地差分隐私 /
- 空间范围查询 /
- 网格划分 /
- 随机应答 /
- 约束推理
Abstract: User data collection and analysis with local differential privacy has attracted considerable attention in recent years. The trade-off among the domain size of user data, encoding method, and perturbation method directly constrains the accuracy of spatial range query. To remedy the deficiency caused by the current encoding and perturbating method, this paper employs grid and quadtree to propose an efficient solution, called GT-R, to answer spatial range query. GT-R uses a uniform grid to decompose the data domain, and generate unit sized regions. Based on these regions, an indexing quadtree is built. And then each user encodes his/her data with the quadtree shared from server, and runs the optimal randomized response on each node of the sampled level in the quadtree and reports the sampled level along with the perturbed value. The server accumulates reports from users to reconstruct a quadtree comprising sum of reports from all users. Besides, to boost the accuracy of range query, the server relies on post-processing skill for consistency on the frequency of each node. GT-R method is compared with existing methods on the large-scale real datasets. The experimental results show that GT-R outperforms its competitors, achieves the accurate results of spatial range query.
- local differential privacy /
- spatial range query /
- grid decomposition /
- randomized response /
- constrained inference

HTML全文

参考文献(0)

施引文献(35)

期刊类型引用(12)

1.	晏燕，吕雅琴，李飞飞. 基于Huffman编码的移动终端本地差分隐私位置保护. 计算机科学与探索. 2025(03): 802-817 . 百度学术
2.	张治政，张啸剑，王俊清，冯光辉. 结合差分隐私与安全聚集的联邦空间数据发布方法. 计算机应用. 2024(09): 2777-2784 . 百度学术
3.	朱友文，唐聪，吴启晖，张焱. 个性化本地差分隐私机制的研究现状与展望. 南京航空航天大学学报. 2024(05): 784-800 . 百度学术
4.	刘利康，周春来. RCP:本地差分隐私下的均值保护技术. 计算机科学. 2023(02): 333-345 . 百度学术
5.	晏燕，董卓越，徐飞，冯涛. 一种Hilbert编码的本地化位置隐私保护方法. 西安电子科技大学学报. 2023(02): 147-160 . 百度学术
6.	唐涛，张磊，段勇，杨立超，张泽. 混淆查询区域下的电网多维数据聚合查询方法研究. 自动化仪表. 2023(08): 73-78 . 百度学术
7.	晏燕，丛一鸣，Adnan Mahmood，盛权政. 基于深度学习的位置大数据统计发布与隐私保护方法. 通信学报. 2022(01): 203-216 . 百度学术
8.	金媛媛，倪志伟，朱旭辉，陈恒恒，陈千. 基于本地差分隐私的空间数据自适应划分算法. 计算机工程. 2022(05): 136-144 . 百度学术
9.	张啸剑，徐雅鑫，孟小峰. 基于本地化差分隐私的空间数据近似k-近邻查询. 计算机研究与发展. 2022(07): 1610-1624 . 本站查看
10.	曹依然，朱友文，贺星宇，张跃. 效用优化的本地差分隐私集合数据频率估计机制. 计算机研究与发展. 2022(10): 2261-2274 . 本站查看
11.	刘俊岭，刘柏何，邹鑫源，孙焕良 . 面向空间兴趣区域的路线查询. 计算机研究与发展. 2022(11): 2569-2580 . 本站查看
12.	王明月，张兴，李万杰，张青云，李晓会. 面向数据发布的隐私保护技术研究综述. 小型微型计算机系统. 2020(12): 2657-2667 . 百度学术