《计算机应用研究》|Application Research of Computers


Location data privacy protection based on differential privacy mechanism

免费全文下载 (已被下载 次)  
作者 杨理皓,谷科,李威
机构 长沙理工大学 计算机与通信工程学院 综合交通运输大数据智能处理湖南省重点实验室,长沙 410114
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2018)03-0895-06
DOI 10.3969/j.issn.1001-3695.2018.03.054
摘要 位置定位服务技术作为一种全新的移动计算服务,在日常生活中应用广泛。一方面,数据信息共享极大地方便了人们的日常生活,另一方面也存在由于泄露个人敏感信息而产生的弊端,因此如何保护好位置数据是关键。由于位置数据具有价值高和低密度的特性,导致现有的隐私保护方法很难兼顾数据的保护和数据的效用性。基于差分隐私机制的位置数据隐私保护策略通过采用多级查询树的结构来查询和发布保护后的数据,并保持了数据项间的联系。首先构建多级查询树(位置搜索树),然后遍历查询树,使用差分隐私的指数机制来选取访问频率高的k项,最后通过拉普拉斯机制给选取的k项进行加噪。实验表明,相比于其他保护策略,基于差分隐私机制的位置数据隐私保护策略可用性和数据保护程度高,算法运行时间少,效率更高。
关键词 位置数据;访问频率;差分隐私保护;多级查询树
基金项目 国家自然科学基金资助项目(61402055,61462048,61504013)
本文URL http://www.arocmag.com/article/01-2018-03-054.html
英文标题 Location data privacy protection based on differential privacy mechanism
作者英文名 Yang Lihao, Gu Ke, Li Wei
机构英文名 HunanProvincialKeyLaboratoryofIntelligentProcessingofBigDataonTransportation,SchoolofComputer&CommunicationEngineering,ChangshaUniversityofScience&Technology,Changsha410114,China
英文摘要 Now many applications of location data have facilitated people’s daily life, so location data service is called a kind of new mobile computing service. However, publishing location data may divulge individual sensitive information and then affect people’s normal life. On the other hand, if they cannot mine and share data information, data will lose its value for serving people’s society. So, it is double-edged sword that how to use location data. Currently many existing privacy protection schemes can not provide the balance of utility and protection for data. Furthermore, as location data is discrete, some existing privacy protection schemes are difficult to protect location data in data mining. This paper proposed that a location data privacy protection scheme was based on differential privacy mechanism, which employed the structure of multilevel query tree to query and publish location data result on database. In the proposed scheme, they first constructed the structure of multi-level query tree on database, and then made double processes of selecting data on accessing frequencies by the exponential mechanism and one process of adding noises to accessing frequencies by the Laplace’s mechanism on the multi-level query tree. Compared with other schemes, what the experiments show is the data’s availability and privacy protection level of the proposed scheme is more higher, and the running time of the proposed algorithms is less.
英文关键词 location data; accessing frequencies; differential privacy protection; multi-level query tree
参考文献 查看稿件参考文献
  [1] Li Guojie. The scientific value of the study in big data[J] . Communications of the China Computer Fedaration, 2012, 8(9):8-15.
[2] Samarati P, Sweeney L. Generalizing data to provide anonymity when disclosing information[C] //Proc of the 7th ACM SIGACTSIGMOD-SIGART Symposium on Principles of Database Systems. New York:ACM Press, 1998:188-202.
[3] Sweeney L. k-anonymity:a model for protecting privacy[J] . International Journal of Uncertainty, Fuzzines and Knowledge-Based Systems, 2012, 10(5):557-570.
[4] Wong R C W, Li J, Fu A W C, et al. (a, k)-anonymity:an enhanced k-anonymity model for privacy-preserving data publishing[C] //Proc of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press, 2006:754-759.
[5] LeFevre K, DeWitt D J, Ramakrishnan R. Mondrian multidimensio-nal k-anonymity[C] //Proc of the 22nd International Conference on Data Engineering, 2006.
[6] Machanavajjhala A, Gehrke J, Kifer D, et al. l-diversity:privacy beyond k-anonymity[C] //Proc of the 22nd IEEE International Conference on Data Engineering. 2006.
[7] Xiao Xiaokui, Tao Yufei. Anatomy:simple and effective privacy preservation[C] //Proc of the 32nd International Conference on Very Large Data Bases. 2006:139-150.
[8] Tao Yufei, Xiao xiaokui. Personalized privacy preservation[C] // Proc of ACM SIGMOD International Conference on Management of Data. New York:ACM Press, 2006:229-240.
[9] Xu Jian, Wang Wei, Pei Jian, et al. Utility-based anonymization using local recoding[C] //Proc of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2006:785-790.
[10] Li Ninghui, Li Tiancheng, Venkatasubramanian S. t-closeness:privacy beyond k-anonymity and l-diversity[C] //Proc of the 23rd IEEE International Conference on Data Engineering. Piscataway:IEEE Press, 2007:106-115.
[11] Wong R C W, Fu A W C, Wang K, et al. Minimality attack in privacy preserving data publishing[C] //Proc of the 33rd International Conference on Very Large Databases. 2007:543-554.
[12] Tao Yufei, Xiao Xiaokui, Li Jiexing, et al. On anti-corruption privacy preserving publication[C] //Proc of the 24th International Conference on Data Engineering. 2008:725-734.
[13] Backstrom L, Dwork C, Kleinberg J. Wherefore art thou R3579X? anonymized social networks, hiddern patterns and structural steganography[C] //Proc of the 16th International Conference on World Wide Web. New York:ACM Press, 2007:181-190.
[14] Zheleva E, Getoor L. Preserving the privacy of sensitive relationships in graph data[C] //Proc of the 1st ACM SIGKDD Workshop on Privacy, Security, and Trust in KDD. New York:ACM Press, 2007:153-171.
[15] Korolova A, Motwani R, Nabar S U, et al. Link privacy in social networks[C] //Proc of the 24th International Conference on Data Engineering. 2008:1355-1357.
[16] De Cristofaro E, Soriente C, Tsudik G, et al. Hummingbird:privacy at the time of Twitter[C] //Proc of IEEE Symposium on Security and Privacy. Piscataway:IEEE Press, 2012:285-299.
[17] Beresford A R, Rice A, Skehin N, et al. MockDroid:trading privacy for application functionality on smartphones[C] //Proc of the 12th Workshop on Mobile Computing Systems and Applications. New York:ACM Press, 2011:49-54.
[18] Wang Lu, Meng Xiaofeng. Location privacy preservation in big data era:a survey[J] . Journal of Software, 2014, 25(4):693-712.
[19] Huo Zheng, Meng Xiaofeng. A survey of trajectory privacy-preserving techniques[J] . Chinese Journal of Computers, 2011, 34(10):1820-1830.
[20] Bamba B, Liu Ling, Pesti P, et al. Supporting anonymous location queries in mobile environments with privacy grid[C] //Proc of the 17th International Conference on World Wide Web. New York:ACM Press, 2008:237-246.
[21] Liu Ling. From data privacy to location privacy:models and algorithms[C] //Proc of the 33rd International Conference on Very Large Data Bases. New York:ACM Press, 2007:1429-1430.
[22] Liu Fuyu, Hua K A, Cai Ying. Query l-diversity in location-based services[C] //Proc of the 10th International Conference on Mobile Data Management. 2009:436-442.
[23] Dwork C. Differential privacy in new settings[C] //Proc of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms Society for Industrial and Applied Mathematics. New York:ACM Press, 2010:174-183.
[24] Li Y D, Zhang Zhenjie, Winslett M, et al. Compressive mechanism:utilizing sparse representation in differential privacy[C] //Proc of the 10th Annual ACM Workshop on Privacy in the Electronic Society. New York:ACM Press, 2011:177-182.
[25] Ouyang Jia, Yin Jian, Liu Shaopeng, et al. An effective differential privacy transaction data publication strategy[J] . Journal of Computer Research and Development, 2014, 51(10):2195-2205.
[26] Zhang Xiaojian, Wang Miao, Meng Xiaofeng. An accurate method for mining top-k frequent pattern under differential privacy[J] . Journal of Computer Research and Development, 2014, 51(1):104-114.
[27] Dwork C. The promise of differential privacy:a tutorial on algorithmic techniques[C] //Proc of Foundations of Computer Science. Piscataway:IEEE Press, 2011:1-2.
[28] McSherry F, Talwar K. Mechanism design via differential privacy[C] //Proc of Foundations of Computer Science (FOCS). Piscataway:IEEE Press, 2007:94-103.
[29] Jun-Ichi A, Katsushi M, Takashi S. An efficient implementation of trie structures[J] . Software:Practice and Experience, 1992, 22(9):695-721.
[30] Shi Chuang, Zhao Qile, Hu Zhigang, et al. Precise relative positioning using real tracking data from COMPASS GEO and IGSO satellites[J] . GPS Solutions, 2013, 17(1):103-119.
收稿日期 2016/12/13
修回日期 2017/2/3
页码 895-900
中图分类号 TP309.2
文献标志码 A