JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2018, Vol. 53 ›› Issue (9): 12-22.doi: 10.6040/j.issn.1671-9352.0.2017.418

Previous Articles     Next Articles

Differential privacy partitioning algorithm based on adaptive density grids

YAN Yan1, 2, HAO Xiao-hong1*   

  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

PDF (PC)

556

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

CLC Number: 

  • TP309
[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.
[1] BI Xiao-di, LIANG Ying, SHI Hong-zhou, TIAN Hui. Aparameterized location privacy protection method based on two-level Anonymity [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(5): 75-84.
[2] KANG Hai-yan, MA Yue-lei. Survey on application of data mining via differential privacy [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(3): 16-23.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd