JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE) ›› 2015, Vol. 45 ›› Issue (1): 24-29.doi: 10.6040/j.issn.1672-3961.2.2014.120

Previous Articles     Next Articles

Differentially privacy two-dimensional dataset partitioning publication algorithm based on kd-tree

HUANG Siyong, CHEN Tingting, LU Qing, WU Yingjie, YE Shaozhen   

  1. College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China
  • Received:2014-05-23 Revised:2014-11-20 Published:2014-05-23

PDF (PC)

829

Abstract: The existing differentially privacy two-dimensional dataset partitioning publication approaches might result in over-partitioning of certain local regions thus lower the query accuracy. To solve this problem, a new differentially privacy partitioning publication algorithm based on kd-tree for two-dimensional dataset (kd-PPDP) was proposed.To reduce the noise generated by the Laplace mechanism and improve the accuracy of query, the new approach which was inspired by the core thought of kd-tree took the gridding data distribution into account and merged adjacent grid units with similar information heuristically to prevent local over-partitioning. The new approach was compared with the existing differentially privacy partitioning publication approachs based on grid structure in terms of query error and time complexity. Experimental results showed that the approach was feasible and effective.

Key words: two-dimensional dataset, privacy preserving, data partitioning publication, differential privacy, kd-tree

CLC Number: 

  • TP311.13
[1] 周水庚,李丰,陶宇飞,等.面向数据库应用的隐私保护研究综述[J]. 计算机学报, 2009, 32(5):847-858. ZHOU Shuigeng, LI Feng, TAO Yufei, et al. Privacy preservation in database applications:A survey[J]. Chinese Journal of Computers, 2009, 32(5):847-858.
[2] FUNG BCM, WANG Ke, CHEN Rui, et al. Privacy-preserving data publishing:A survey on recent developments[J]. ACM Computing Surveys, 2010, 42(4):1-53.
[3] DWORK C. Differential privacy[C]//Proc of the 33rd Int Colloquium on Automata, Languages and Programming. Berlin:Springer, 2006:1-12.
[4] DWORK C, MCSHERRY F, NISSIM F K, et al. Calibrating noise to sensitivity in private data analysis[C]//Proceedings of the 3rd Theory of Cryptography Conference (TCC). New York, USA:Springer Berlin Heidelberg, 2006:363-385.
[5] SWEENEY L. k-anonymity:A model for protecting privacy[J]. International Journal on Uncertainty, Fuzziness and Knowledge Based Systems, 2002, 10(5):557-570.
[6] MACHANAVAJJHALA A, GEHRKE J, KIFER D, et al. l-diversity:Privacy beyond k-anonymity[C]//Proceedings of IEEE ICDE'06. Piscataway, NJ:IEEE, 2006:24-35.
[7] LI Ninghui, LI Tiancheng. t-closeness:Privacy beyond k-anonymity and l-diversity[C]//Proceedings of IEEE ICDE'07. Piscataway, NJ:IEEE, 2007:106-115.
[8] CHEN R, MOHAMMED N, FUNG B C M, et al. Publishing set-valued data via differential privacy[J]. Proceedings of the VLDB Endowment, 2011, 4(11):1087-1098.
[9] CHEN R, ACS G, CASTELLUCCIA C. Differentially private sequential data publication via variable-length n-grams[C]//Proceedings of the 2012 ACM conference on Computer and communications security.Raleigh, NC, USA:ACM, 2012:638-649.
[10] CHEN R, FUNG B, DESAI B C, et al. Differentially private transit data publication:A case study on the montreal transportation system[C]//Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. Beijing, China:ACM, 2012:213-221.
[11] CORMODE G, PROCOPIUC C, SRIVASTAVA D, et al. Differentially private spatial decompositions[C]//Proceedings of IEEE 28th International Conference on Data Engineering (ICDE), Washington D C. USA:IEEE, 2012:20-31.
[12] QARDAJI W, YANG W, LI N. Differentially private grids for geospatial data[C]//Proceedings of IEEE 29th International Conference on Data Engineering (ICDE). Brisbane, Australia:IEEE, 2013:757-768.
[13] HAY M, RASTOGI V, MIKLAU G, et al. Boosting the accuracy of differentially private histograms through consistency[J]. Proceedings of the VLDB Endowment, 2010, 3(1-2):1021-1032.
[14] McSherry F D. Privacy integrated queries:an extensible platform for privacy-preserving data analysis[C]//Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. Providence, Rhode Island, USA:ACM, 2009:19-30.
[1] SUN Lan, LUO Zhao, WU Ying-jie, WANG Yi-lei. An algorithm for protecting location privacy in road network [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(5): 96-101.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd