差分隐私密度自适应网格划分发布方法

doi:10.6040/j.issn.1671-9352.0.2017.418

山东大学学报（理学版） ›› 2018, Vol. 53 ›› Issue (9): 12-22.doi: 10.6040/j.issn.1671-9352.0.2017.418

差分隐私密度自适应网格划分发布方法

晏燕^1,2,郝晓弘^1*

1.兰州理工大学电气工程与信息工程学院, 甘肃兰州 730050;2.兰州理工大学计算机与通信学院, 甘肃兰州 730050

收稿日期:2017-08-21 出版日期:2018-09-20 发布日期:2018-09-10
作者简介:晏燕(1980— ),女,博士研究生,副教授,研究方向为隐私保护技术、多媒体信息安全. E-mail:yanyan@lut.cn*通信作者简介:郝晓弘(1960— ),男,硕士,教授,博士生导师,研究方向为复杂系统理论、智能控制技术. E-mail:haoxh@lut.com
基金资助:
国家自然科学基金资助项目(61762059);甘肃省青年科技基金计划项目(1310RJYA004)

Differential privacy partitioning algorithm based on adaptive density grids

YAN Yan^{1, 2}, HAO Xiao-hong^1*

1. School of Electrical and Information Engineering, Lanzhou University of Technology, Lanzhou 730050, Gansu, China;
2. School of Computer and Communication, Lanzhou University of Technology, Lanzhou 730050, Gansu, China

Received:2017-08-21 Online:2018-09-20 Published:2018-09-10

摘要/Abstract

摘要： 为了进一步均衡噪声误差和均匀假设误差对二维划分发布带来的影响,提出一种新的分层差分隐私位置信息划分发布算法。首先将位置空间聚类形成第一层密度自适应网格,然后对不同性质的密度区块采取不同的二次划分方法,在降低均匀假设误差的同时避免了大量空结点引入的噪声误差。在采用分层划分策略的同时,结合差分隐私模型的串行组合特性,对2个阶段的划分结果添加不同隐私预算的Laplace噪声,总体上实现对发布数据的ε-差分隐私保护。实验证明,该算法在改善区域计数查询精度方面具有较好的效果,能够节省不必要的划分过程,有效提高了算法的运行效率。

关键词: 空间划分, 位置大数据, 差分隐私, 密度自适应网格

Abstract: In order to balance the influence of noise error and uniform hypothesis error for the two-dimensional partitioning publishing, a new hierarchical differential privacy partitioning algorithm DP-ADG is proposed. Firstly, the position space is clustered to form the density adaptive grids in the first layer. Then in the second layer, different partitioning methods are adopted for different density blocks. The noise error introduced by a large number of null nodes is avoided while reducing the uniform hypothesis error. While using the hierarchical partitioning strategy, different Laplace noise of different privacy budgets is added to the results of two phases according to the sequential composition of differential privacy, in order to realize the overall ε differential privacy protection for the publishing data. Experimental results show that the algorithm has good effect on improving the accuracy of range counting query, saving unnecessary spatial decomposition process, as well as improving the efficiency of the algorithm.

Key words: location big data, differential privacy, spatial decomposition, density adaptive grids

中图分类号:

TP309

晏燕,郝晓弘. 差分隐私密度自适应网格划分发布方法[J]. 山东大学学报（理学版）, 2018, 53(9): 12-22.

YAN Yan, HAO Xiao-hong. Differential privacy partitioning algorithm based on adaptive density grids[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(9): 12-22.

参考文献

[1] 工业和信息化部. 工业和信息化部关于印发大数据产业发展规划(2016—2020年)的通知,工信部规[2016] 412号[R].北京:工业和信息化部,2016.
[2] 冯登国, 张敏, 李昊. 大数据安全与隐私保护[J]. 计算机学报, 2014, 37(1):246-258. FENG Dengguo, ZHANG Min, LI Hao. Big data security and privacy protection[J]. Chinese Journal of Computers, 2014, 37(1):246-258.
[3] 刘雅辉, 张铁赢, 靳小龙, 等. 大数据时代的个人隐私保护[J] , 计算机研究与发展, 2015, 52(1):229-247. LIU Yahui, ZHANG Tieying, JIN Xiaolong, et al. Personal privacy protection in the era of big data[J]. Journal of Computer Research and Development, 2015, 52(1):229-247.
[4] 孟小峰, 张啸剑. 大数据隐私管理[J] , 计算机研究与发展, 2015, 52(2):265-281. MENG Xiaofeng, ZHANG Xiaojian. Big data privacy management[J]. Journal of Computer Research and Development, 2015, 52(2):265-281.
[5] 方滨兴, 贾焰, 李爱平, 等. 大数据隐私保护技术综述[J].大数据, 2016,2(1):1-18. FANG Binxing, JIA Yan, LI Aiping, et al. Privacy preservation in big data: a survey[J]. Big Data Research, 2016, 2(1):1-18.
[6] EMC Education Services. Data science and big data analytics: discovering, analyzing, visualizing and presenting data[M]. New York: Wiley, 2015.
[7] WERNKE M, SKVORTSOV P, DUR F, et al. A classification of location privacy attacks and approaches[J]. Personal and Ubiquitous Computing, 2014, 18:163-175.
[8] TERROVITIS M, POULIS G, MAMOULIS N, et al. Local suppression and splitting techniques for privacy preserving publication of trajectories[J]. IEEE Transactions on Knowledge & Data Engineering, 2017, 29(7):1466-1479.
[9] 张啸剑, 孟小峰. 面向数据发布和分析的差分隐私保护[J]. 计算机学报, 2014, 37(4):927-949. ZHANG Xiaojian, MENG Xiaofeng. Differential privacy in data publication and analysis[J]. Chinese Journal of Computers, 2014, 37(4):927-949.
[10] 彭慧丽, 张啸剑. 基于差分隐私的空间分割研究综述[J]. 燕山大学学报, 2016, 40(3):263-269. PENG Huili, ZHANG Xiaojian. Survey on spatial data decomposition with differential privacy[J]. Journal of Yanshan Univisity, 2016, 40(3):263-269.
[11] CORMODE G, PROCOPIUC C, SRIVASTAVA D, et al. Differentially private spatial decompositions[C] // Proceedings of the 28th International Conference on Data Engineering(ICDE). Washington: IEEE, 2012: 20-31.
[12] 吴英杰, 卢清, 蔡剑平, 等. 基于四分树的差分隐私二维数据划分发布算法[J].华中科技大学学报(自然科学版), 2016, 44(3):99-104. WU Yingjie, LU Qing, CAI Jianping, et al. Differential privacy two-dimensional data partitioning publication algorithm based on quad-tree[J]. Journal of Huazhong University of Science & Technology(Natural Science Edition), 2016, 44(3):99-104.
[13] ZHANG Jun, XIAO Xiaokui, XIE Xing. PrivTree: a differentially private algorithm for hierarchical decompositions[C] // Proceedings of the 36th ACM International Conference on Management of Data. CA: San Francisco, 2016: 155-170.
[14] QARDAJI W, YANG W N, LI N H. Differentially private grids for geospatial data[C] // Proceedings of the 29th International Conference on Data Engineering(ICDE). Brisbane: IEEE, 2013: 757-768.
[15] MIR D J, ISAACMAN S, CACERES R, et al. DP-Where: differentially private modeling of human mobility[C] // Proceedings of 2013 IEEE International Conference on Big Data, 2013: 580-588.
[16] 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. Lausanne: ACM, 2010: 123-134.
[17] 黄泗勇, 陈婷婷, 卢清, 等. 基于Kd-树的差分隐私二维空间数据划分发布方法[J].山东大学学报(工学版), 2015, 45(1):24-29. HUANG Siyong, CHEN Tingting, LU Qing, et al. Differential privacy two-dimensional dataset partitioning publication algorithm based on Kd-tree[J]. Journal of Shandong University(Engineering Science), 2015, 45(1):24-29.
[18] 张琳, 刘彦, 王汝传. 位置大数据服务中基于差分隐私的数据发布技术[J]. 通信学报, 2016, 37(9):46-54. ZHANG Lin, LIU Yan, WANG Ruchuan. Location publishing technology based on differential privacy-preserving for big data services[J]. Journal on Communications, 2016, 37(9):46-54.
[19] 王豪, 徐正全, 熊礼治, 等. CLM:面向轨迹发布的差分隐私保护方法[J]. 通信学报, 2017, 38(6):85-96. WANG Hao, XU Zhengquan, XIONG Lizhi, et al. CLM: differential privacy protection method for trajectory publishing[J]. Journal on Communications, 2017, 38(6):85-96.
[20] DWORK C, MCSHERRY F, NISSIM K, et al. Calibrating noise to sensitivity in private data analysis[C] // Proceedings of the 3th Theory of Cryptography Conference(TCC). Berlin: Springer-Verlag, 2006: 265-284.
[21] DWORK C. Differential privacy[C] // Proceedings of the 33rd International Colloquium on Automata, Languages and Programming(ICALP). Berlin:Springer-Verlag, 2006: 1-12.
[22] MCSHERRY F. Privacy integrated queries: an extensible platform for privacy-preserving data analysis[C] // Proceedings of the ACM SIGMOD International Conference on Management of Data(SIGMOD).New York:ACM, 2009: 19-30.
[23] MCSHERRY F, TALWAR K. Mechanism design via differential privacy[C] // Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science(Focs'07). Washington: IEEE Computer Society, 2007: 94-103.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

差分隐私密度自适应网格划分发布方法

Differential privacy partitioning algorithm based on adaptive density grids

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

多维度评价

本文评价

推荐阅读 0

[1]	毕晓迪,梁英,史红周,田辉. 一种基于隐私偏好的二次匿名位置隐私保护方法[J]. 山东大学学报（理学版）, 2017, 52(5): 75-84.
[2]	康海燕,马跃雷. 差分隐私保护在数据挖掘中应用综述[J]. 山东大学学报（理学版）, 2017, 52(3): 16-23.