基于本地差分隐私的空间数据自适应划分算法

doi:10.19678/j.issn.1000-3428.0062382

计算机工程 ›› 2022, Vol. 48 ›› Issue (5): 136-144. doi: 10.19678/j.issn.1000-3428.0062382

基于本地差分隐私的空间数据自适应划分算法

金媛媛^1,2, 倪志伟^1,2, 朱旭辉^1,2, 陈恒恒^1,2, 陈千^1,2

1. 合肥工业大学管理学院, 合肥 230009;
2. 合肥工业大学过程优化与智能决策教育部重点实验室, 合肥 230009

收稿日期:2021-08-17 修回日期:2021-09-30 发布日期:2022-05-10
作者简介:金媛媛(1998—),女,硕士研究生,主研方向为信息安全、数据管理;倪志伟(通信作者),教授、博士;朱旭辉,讲师、博士;陈恒恒,硕士;陈千,博士。
基金资助:
国家自然科学基金“大数据环境下协同商务智能构建中的关键技术研究”（91546108）；安徽省科技重大专项“面向混合云数据中心的隐私安全防护关键技术及其虚拟化设备研发”（201903a05020020）。

Spatial Data Adaptive Partition Algorithm Based on Local Differential Privacy

JIN Yuanyuan^1,2, NI Zhiwei^1,2, ZHU Xuhui^1,2, CHEN Hengheng^1,2, CHEN Qian^1,2

1. School of Management, Hefei University of Technology, Hefei 230009, China;
2. Key Laboratory of Process Optimization and Intelligent Decision-Making, Ministry of Education, Hefei University of Technology, Hefei 230009, China

Received:2021-08-17 Revised:2021-09-30 Published:2022-05-10

摘要/Abstract

摘要： 空间位置数据分布通常具有不均匀性，不同位置区域的密度差异较大，在本地差分隐私模型中无法直接获取用户真实的位置数据，使得空间位置划分方法受到限制以及数据发布存在查询精度低、通信代价大等问题。为在本地差分隐私模型下的大规模空间数据采集和发布过程中进行空间划分，提出一种空间数据分层自适应划分算法KDG-HT。通过收集部分用户的数据来初步获取区域的分布情况，采用KD-树的思想划分区域，并利用抽样技术对用户进行分组，根据分组用户统计结果所提供的先验知识来完成多层细粒度划分。在此基础上，结合差分隐私模型的并行组合特性分层扰动用户数据，从总体上实现发布数据的ε-差分隐私保护。实验结果表明，KDG-HT算法适用于具有不同数据分布情况的大规模空间数据集，查询精度及运行效率优于RAPPOR、UG、GT-R等算法，其中与GT-R算法相比，KDG-HT算法发布数据的查询精度最高提升3倍，运行效率提高17%。

关键词: 本地差分隐私, 空间自适应划分, 用户随机采样, 空间范围查询, 随机响应

Abstract: The distribution of spatial location data is typically uneven, and the density of different location areas varies significantly.In the local differential privacy model, the actual location data of users cannot be obtained directly, which limits the spatial location segmentation method.Additionally, problems exist in data publishing, such as low query accuracy and high communication cost.To segment a space during large-scale spatial data acquisition and distribution using the local differential privacy model, a hierarchical adaptive spatial data partition algorithm, KDG-HT, is proposed.By acquiring the data of some users to preliminarily obtain the distribution of a region, the region can be segmented using the concept of the KD-tree, and the users can be categorized via sampling technology.By applying prior knowledge provided by the statistical results of the grouped users, the multilayer fine-grained segmentation is completed.Subsequently, combined with the parallel combination characteristics of the differential privacy model, the user data are disturbed hierarchically, and the publishing data are realized as a complete ε-differential privacy protection.Experimental results show that the KDG-HT algorithm is suitable for large-scale spatial datasets with different data distributions, and that its query accuracy and operation efficiency are better than those of RAPPOR, UG, GT-R, and other algorithms.Compared with the GT-R algorithm, the KDG-HT algorithm can improve the query accuracy of published data by up to three times and the operation efficiency by 17%.

Key words: local differential privacy, spatial adaptive partition, user random sampling, spatial range query, randomized response

中图分类号:

TP309.2

金媛媛, 倪志伟, 朱旭辉, 陈恒恒, 陈千. 基于本地差分隐私的空间数据自适应划分算法[J]. 计算机工程, 2022, 48(5): 136-144.

JIN Yuanyuan, NI Zhiwei, ZHU Xuhui, CHEN Hengheng, CHEN Qian. Spatial Data Adaptive Partition Algorithm Based on Local Differential Privacy[J]. Computer Engineering, 2022, 48(5): 136-144.

https://www.ecice06.com/CN/Y2022/V48/I5/136

图/表 8

20220723173900

20220723173904

20220723173909

20220723173914

20220723173918

20220723173921

20220723173924

20220723173928

参考文献

[1] LI X, ZHAO Y, ZHOU X F, et al.Consensus-based group task assignment with social impact in spatial crowdsourcing[J].Data Science and Engineering, 2020, 5(4):375-390.
[2] TO H, GHINITA G, SHAHABI C.A framework for protecting worker location privacy in spatial crowdsourcing[J].Proceedings of the VLDB Endowment, 2014, 7(10):919-930.
[3] CHEN R, LI H R, QIN A K, et al.Private spatial data aggregation in the local setting[C]//Proceedings of the 32nd IEEE International Conference on Data Engineering.Washington D.C., USA:IEEE Press, 2016:289-300.
[4] 郑振青, 毋小省, 王辉, 等.移动社交网络中的轨迹隐私PTPM保护方法[J].小型微型计算机系统, 2021, 42(10):2153-2160. ZHENG Z Q, WU X S, WANG H, et al.PTPM protection method for trajectory privacy in mobile social network[J]. Journal of Chinese Computer Systems, 2021, 42(10):2153-2160.(in Chinese)
[5] DWORK C.Differential privacy[C]//Proceedings of the 33rd International Conference on Automata, Languages and Programming.Washington D.C., USA:IEEE Press, 2006:1-12.
[6] HUA J Y, TONG W, XU F Y, et al.A geo-indistinguishable location perturbation mechanism for location-based services supporting frequent queries[J].IEEE Transactions on Information Forensics and Security, 2018, 13(5):1155-1168.
[7] CORMODE G, PROCOPIUC C, SRIVASTAVA D, et al.Differentially private spatial decompositions[C]//Proceedings of 2012 IEEE International Conference on Data Engineering.Washington D.C., USA:IEEE Press, 2012:20-31.
[8] QARDAJI W, YANG W N, LI N H.Differentially private grids for geospatial data[C]//Proceedings of IEEE International Conference on Data Engineering.Washington D.C., USA:IEEE Press, 2013:757-768.
[9] ZHANG J, XIAO X K, XIE X.PrivTree:a differentially private algorithm for hierarchical decompositions[C]//Proceedings of 2016 International Conference on Management of Data.Washington D.C., USA:IEEE Press, 2016:155-170.
[10] INAN A, KANTARCIOGLU M, GHINITA G, et al.Private record matching using differential privacy[C]//Proceedings of the 13th International Conference on Extending Database Technology.Washington D.C., USA:IEEE Press, 2010:123-134.
[11] MCSHERRY F, TALWAR K.Mechanism design via differential privacy[C]//Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science.Washington D.C., USA:IEEE Press, 2007:94-103.
[12] 金凯忠, 张啸剑, 彭慧丽.KD-TSS:精确隐私空间分割方法[J].计算机科学与探索, 2017, 11(10):1579-1590. JIN K Z, ZHANG X J, PENG H L.KD-TSS:accurate method for private spatial decomposition[J].Journal of Frontiers of Computer Science and Technology, 2017, 11(10):1579-1590.(in Chinese)
[13] ERLINGSSON Ú, PIHUR V, KOROLOVA A.RAPPOR:randomized aggregatable privacy-preserving ordinal response[C]//Proceedings of 2014 ACM SIGSAC Conference on Computer and Communications Security.New York, USA:ACM Press, 2014:1054-1067.
[14] KAIROUZ P, BONAWITZ K, RAMAGE D.Discrete distribution estimation under local privacy[C]//Proceedings of the 33rd International Conference on Machine Learning.New York, USA:ACM Press, 2016:2436-2444.
[15] BASSILY R, SMITH A.Local, private, efficient protocols for succinct histograms[C]//Proceedings of the 47th Annual ACM Symposium on Theory of Computing.New York, USA:ACM Press, 2015:127-135.
[16] 阚莹莹, 曹天杰.基于分组无关问题模型的隐私保护算法[J].计算机工程, 2010, 36(5):79-80, 83. KAN Y Y, CAO T J.Privacy-preserving algorithm based on grouping unrelated-question model[J].Computer Engineering, 2010, 36(5):79-80, 83.(in Chinese)
[17] LI Z T, WANG T H, LOPUHAÄ-ZWAKENBERG M, et al.Estimating numerical distributions under local differential privacy[C]//Proceedings of 2020 ACM SIGMOD International Conference on Management of Data.New York, USA:ACM Press, 2020:621-635.
[18] SHEN Z X, XIA Z H, YU P P.PLDP:personalized local differential privacy for multidimensional data aggregation[J].Security and Communication Networks, 2021, 15:6684179.
[19] KIM J W, KIM D H, JANG B.Application of local differential privacy to collection of indoor positioning data[J].IEEE Access, 2018, 6:4276-4286.
[20] 张啸剑, 付楠, 孟小峰.基于本地差分隐私的空间范围查询方法[J].计算机研究与发展, 2020, 57(4):847-858. ZHANG X J, FU N, MENG X F.Towards spatial range queries under local differential privacy[J].Journal of Computer Research and Development, 2020, 57(4):847-858.(in Chinese)
[21] 霍峥, 张坤, 贺萍, 等.满足本地化差分隐私的众包位置数据采集[J].计算机应用, 2019, 39(3):763-768. HUO Z, ZHANG K, HE P, et al.Crowdsourcing location data collection for local differential privacy[J].Journal of Computer Applications, 2019, 39(3):763-768.(in Chinese)
[22] WARNER S L.Randomized response:a survey technique for eliminating evasive answer bias[J].Journal of the American Statistical Association, 1965, 60(309):63-66.
[23] 叶青青, 孟小峰, 朱敏杰, 等.本地化差分隐私研究综述[J].软件学报, 2018, 29(7):1981-2005. YE Q Q, MENG X F, ZHU M J, et al.Survey on local differential privacy[J].Journal of Software, 2018, 29(7):1981-2005.(in Chinese)
[24] 李效光, 李晖, 李凤华, 等.差分隐私综述[J].信息安全学报, 2018, 3(5):92-104. LI X G, LI H, LI F H, et al.A survey on differential privacy[J].Journal of Cyber Security, 2018, 3(5):92-104.(in Chinese)
[25] DUCHI J C, JORDAN M I, WAINWRIGHT M J.Local privacy and statistical minimax rates[C]//Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science.Washington D.C., USA:IEEE Press, 2013:429-438.

选择文件类型/文献管理软件名称

选择包含的内容

基于本地差分隐私的空间数据自适应划分算法

Spatial Data Adaptive Partition Algorithm Based on Local Differential Privacy

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献

相关文章 1

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于本地差分隐私的空间数据自适应划分算法

Spatial Data Adaptive Partition Algorithm Based on Local Differential Privacy

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献

相关文章 1

编辑推荐

Metrics

本文评价