Research on Trajectory Privacy Preserving Method Based on Trajectory Characteristics and Dynamic Proximity
-
摘要: 移动社会网络的兴起以及移动智能终端的发展产生了大量的时空轨迹数据,发布并分析这样的时空数据有助于改善智能交通,研究商圈的动态变化等.然而,如果攻击者能够识别出轨迹对应的用户身份,将会严重威胁到用户的隐私信息.现有的轨迹匿名算法在度量相似性时仅考虑轨迹在采样点位置的邻近性,忽略轨迹位置的动态邻近性,因此产生的匿名轨迹集合可用性相对较低.针对这一问题,本文提出了邻域扭曲密度和邻域相似性的概念,充分考虑轨迹位置的动态邻近性,并分别提出了基于邻域相似性和邻域扭曲密度的轨迹匿名算法;前者仅考虑了轨迹位置的动态邻近性,后者不仅能衡量轨迹位置的动态邻近性,而且在聚类过程中通过最小化邻域扭曲密度来减少匿名集合的信息损失.最后,在合成轨迹数据集和真实轨迹数据集上的实验结果表明,本文提出的算法具有更高的数据可用性.Abstract: The rise of mobile social networks as well as mobile intelligent terminal has generated a lot of spatial-temporal trajectory data, publishing and analyzing such data is essential to improve transportation, to understand the dynamics of the economy in a region, etc. However, it will be a serious threat to the user's privacy, if adversary is able to identify user's identity corresponding to the trajectory. While calculating similarity of trajectories, the existing methods consider only locations proximity of the sampling point in the trajectory, and ignore the dynamic proximity of locations in the trajectory. So the produced trajectory anonymity set has a low utility. To solve this problem, we first present the concept of neighborhood similarity and neighborhood distortion density to fully consider the dynamics proximity of locations in the trajectory, and then propose two algorithms, i.e., trajectory anonymity algorithm based on neighborhood similarity and trajectory anonymity algorithm based on trajectory neighborhood distortion density. The former one only considers the dynamics proximity of locations in the trajectory, while the latter one also reduces information loss of anonymous collection by minimizing neighborhood distortion density during the clustering process. Finally, experimental results on a synthetic data set and a real-life data set demonstrate that our method offers better utility than comparable previous proposals in the literature.
-
[1] Li Jian-Zhong, Liu Xian-Min. An impotant aspect of big data: data usability. Journal of Computer Research and Development, 2013, 50(6): 1147-1162(李建中, 刘显敏. 大数据的一个重要方面: 数据可用性. 计算机研究与发展, 2013, 50(6): 1147-1162) [2] Liu Da-You, Chen Hui-Ling, Qi Hong, Yang Bo. Advances in spatiotemporal data mining. Journal of Computer Research and Development, 2013, 50(2): 225-239(刘大有, 陈慧灵, 齐红, 杨博. 时空数据挖掘研究进展. 计算机研究与发展, 2013, 50(2): 225-239) [3] Han Jian-Min, Yu Juan, Yu Hui-Qun, Jia Dong. A multi-level l-diversity model for numerical sensitive attributes. Journal of Computer Research and Development, 2011, 48(1): 147-158(韩建民, 于娟, 虞慧群, 贾洞. 面向数值型敏感属性的分级l-多样性模型. 计算机研究与发展, 2011, 48(1): 147-158) [4] Han Jian-Min, Cen Ting-Ting, Yu Hui-Qun. Research in microaggregation algorithm for k-anonymization. Acta Electronica Sinica, 2008, 36(10): 2021-2029(韩建民, 岑婷婷, 虞慧群. 数据表k-匿名化的微聚集算法研究. 电子学报, 2008, 36(10): 2021-2029) [5] Ni Wei-Wei, Xu Li-Zhen, Chong Zhi-Hong, Wu Ying-Jie, Liu Teng-Teng, Sun Zhi-Hui. A privacy-preserving data perturbation algorithm based on neighborhood entropy. Journal of Computer Research and Development, 2009, 46(3): 498-504(倪巍伟, 徐立臻, 崇志宏, 吴英杰, 刘腾腾, 孙志挥. 基于邻域属性熵的隐私保护数据干扰方法. 计算机研究与发展, 2009, 46(3): 498-504) [6] Yang Jing, Wang Bo. Personalized l-diversity algorithm for multiple sensitive attributes based on minimum selected degree first. Journal of Computer Research and Development, 2012, 49(9): 2603-2610(杨静, 王波. 一种基于最小选择度优先的多敏感属性个性化l-多样性算法. 计算机研究与发展, 2012, 49(9): 2603-2610) [7] Wang Bo, Yang Jing. A personalized privacy anonymous method based on inverse clustering. Acta Electronica Sinica, 2012, 40(5): 883-890(王波, 杨静. 一种基于逆聚类的个性化隐私匿名方法. 电子学报, 2012, 40(5): 883-890) [8] Zhou Shui-Geng, Li Feng, Tao Yu-Fei. Privacy preservation in database applications: a survey. Chinese Journal of Computers, 2009, 32(5): 847-861(周水庚, 李丰, 陶宇飞. 面向数据库应用的隐私保护研究综述. 计算机学报, 2009, 32(5): 847-861) [9] Xiong Ping, Zhu Tian-Qing. A data anonymization approach based on impurity gain and hierarchical clustering. Journal of Computer Research and Development, 2012, 49(7): 1545-1552(熊平, 朱天清. 基于杂度增益与层次聚类的数据匿名方法. 计算机研究与发展, 2012, 49(7): 1545-1552) [10] Samarati P, Sweeney L. Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression. In: Proceedings of the 1998 IEEE Symposium on Research in Security and Privacy. Palo alto, CA: IEEE, 1998. 1-19 [11] Sweeney L. k-anonymity: a model for protecting privacy. International Journal on Uncertainty Fuzziness and Knowledge-based Systems, 2002, 10(5): 557-570 [12] Domingo-Ferrer J, Sramka M, Trujillo-Rasa R. Privacy-preserving publication of trajectories using microaggregation. In: Proceedings of the 3rd ACM SIGSPATIAL International Workshop on Security and Privacy in GIS and LBS. California, USA: ACM, 2010. 26-33 [13] Monreale A, Andrienko G L, Andrienko N V, Giannotti F, Pedreschi D, Rinzivillo S. Movement data anonymity through generalization. Transactions on Data Privacy, 2010, 3(2): 91-121 [14] Abul O, Bonchi F, Nanni M. Never walk alone: uncertainty for anonymity in moving objects databases. In: Proceedings of the 24th International Conference on Data Engineering. Cancun: IEEE, 2008. 376-385 [15] Abul O, Bonchi F, Nanni M. Anonymization of moving objects databases by clustering and perturbation. Information Systems, 2010, 35(8): 884-910 [16] Gruteser M, Grunwald D. Anonymous usage of location-based services through spatial and temporal cloaking. In: Proceedings of the 1st International Conference on Mobile Systems, Applications and Services. San Francisco, USA: ACM, 2003. 31-42 [17] Huo Z, Huang Y, Meng X F. History trajectory privacy-preserving through graph partition. In: Proceedings of the 1st International Workshop on Mobile Location-based Service. Beijing, China: ACM, 2011. 71-78 [18] Chen L, M T, Oria V. Robust and fast similarity search for moving object trajectories. In: Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. Baltimore, Maryland: ACM, 2005. 491-502 [19] Tiakas E, Papadopoulos A N, Djordjevic-Kajan S. Searching for similar trajectories in spatial networks. Journal of Systems and Software, 2009, 82(5):772-788 [20] Gao S, Ma J F, Sun C, Li X H. Balancing trajectory privacy and data utility using a personalized anonymization model. Journal of Network and Computer Applications, 2014, 38(1):125-134 [21] Pan Xiao, Hao Xing, Meng Xiao-Feng. Privacy preserving towards continuous query in location-based services. Journal of Computer Research and Development, 2010, 47(1): 121-129(潘晓, 郝兴, 孟小峰. 基于位置服务中的连续查询隐私保护研究. 计算机研究与发展, 2010, 47(1): 121-129) [22] Huo Zheng, Meng Xiao-Feng. A survey of trajectory privacy-preserving techniques. Chinese Journal of Computers, 2011, 34(10): 1820-1830(霍峥, 孟小峰. 轨迹隐私保护技术研究. 计算机学报, 2011, 34(10): 1820-1830) [23] You T H, Peng W C, Lee W C. Protecting moving trajectories with dummies. In: Proceedings of the 8th International Conference on Mobile Data Management. Mannheim, Germany: IEEE, 2007. 278-282 [24] Gao S, Ma J F, Shi W S, Zhan G X. LTPPM: a location and trajectory privacy protection mechanism in participatory sensing. Wireless Communications and Mobile Computing, 2012, doi: 10.1002/wcm.2324 [25] Terrovitis M, Mamoulis N. Privacy preservation in the publication of trajectories. In: Proceedings of the 9th International Conference on Mobile Data Management. Beijing, China: IEEE, 2008. 65-72 [26] Chen R, Fung B C M, Mohammed N, Desai B C, Wang K. Privacy-preserving trajectory data publishing by local suppression. Information Sciences, 2013, 231: 83-97 [27] Nergiz M E, Atzori M, Saygin Y, G B. Towards trajectory anonymization: a generalization-based approach. In: Proceedings of the SIGSPATIAL ACM GIS 2008 International Workshop on Security and Privacy in GIS and LBS. Irvine, California, USA: ACM, 2008. 52-61 [28] Nergiz M E, Atzori M, Saygin Y, G B. Towards trajectory anonymization: a generalization-based approach. Transactions on Data Privacy, 2009, 2(1): 47-75 [29] Huo Z, Meng X F, Hu H B, Huang Y. You can walk alone: trajectory privacy-preserving through significant stays protection. In: Proceedings of the 17th International Conference on Database Systems for Advanced Applications. Busan, South Korea: ACM, 2012. 351-366 [30] Domingo-Ferrer J, Trujillo-Rasua R. Microaggregation- and permutation-based anonymization of movement data. Information Sciences, 2012, 208: 55-80 [31] Xiong Ping, Zhu Tian-Qing, Wang Xiao-Feng. A survey on differential privacy and application. Chinese Journal of Computers, 2014, 37(1): 101-122(熊平, 朱天清, 王晓峰. 差分隐私保护及其应用. 计算机学报, 2014, 37(1): 101-122) [32] Zhang Xiao-Jian, Meng Xiao-Feng. Differential privacy in data publication and analysis. Chinese Journal of Computers, 2014, 37(4): 927-949(张啸剑, 孟小峰. 面向数据发布和分析的差分隐私保护. 计算机学报, 2014, 37(4): 927-949) [33] Chen R, Desai B C, Sossou N M. Differentially private transit data publication: a case study on the montreal transportation system. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Beijing, China: ACM, 2012. 213-221 [34] LeFevre K, DeWitt D, Ramakrishnan R. Mondrian multidimensional k-anonymity. In: Proceedings of the 22nd International Conference on Data Engineering. Atlanta, Georgia USA: IEEE, 2006. 25-36 [35] Piorkowski M, Sarafijanovoc-Djukic N, Grossglauser M. A parsimonious model of mobile partitioned networks with clustering. In: Proceedings of the 1st International Conference on Communication Systems and Networks. Bangalore, India: IEEE, 2009. 1-10 [36] Song Jin-Ling, Liu Guo-Hua. Selection algorithm for optimized k-values in k-anonymity model. Journal of Chinese Computer Systems, 2011, 32(10): 1987-1993(宋金玲, 刘国华. k-匿名隐私保护模型中k值的优化选择算法. 小型微型计算机系统, 2011, 32(10): 1987-1993)
点击查看大图
计量
- 文章访问数: 1779
- HTML全文浏览量: 55
- PDF下载量: 1330
- 被引次数: 0