k-CS algorithm: trajectory data privacy-preserving based on semantic location protection

doi:10.11772/j.issn.1001-9081.2017071676

Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (1): 182-187.DOI: 10.11772/j.issn.1001-9081.2017071676

Previous Articles Next Articles

k-CS algorithm: trajectory data privacy-preserving based on semantic location protection

HUO Zheng¹, CUI Honglei², HE Ping¹

1. School of Information Technology, Hebei University of Economics and Business, Shijiazhuang Hebei 050061, China;
2. College of Business, Ningbo Institute of Technology, Zhejiang University, Ningbo Zhejiang 315100, China

Received:2017-07-06 Revised:2017-08-22 Online:2018-01-10 Published:2018-01-22
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61502279), the Natural Science Foundation of Hebei Province (F2015207009), the Scientific Research Projects in Colleges and Universities in Hebei Province (BJ2016019, QN2016179), the Soft Science Project of Ningbo City (2016A10066).

基于语义位置保护的轨迹隐私保护的k-CS算法

霍峥¹, 崔洪雷², 贺萍¹

1. 河北经贸大学信息技术学院, 石家庄 050061;
2. 浙江大学宁波理工学院商学院, 浙江宁波 315100

通讯作者: 霍峥
作者简介:霍峥(1982-),女,河北邯郸人,讲师,博士,CCF会员,主要研究方向:隐私保护、移动对象数据库;崔洪雷(1976-),女,辽宁沈阳人,讲师,博士,主要研究方向:大数据环境下的金融数据应用;贺萍(1982-),女,山东莱阳人,讲师,博士,主要研究方向:无线传感器网络、图优化算法。
基金资助:
国家自然科学基金资助项目（61502279）；河北省自然科学基金资助项目（F2015207009）；河北省高等学校科学技术研究项目（BJ2016019，QN2016179）；宁波市软科学项目（2016A10066）。

Abstract

Abstract: Since the data utility would be sharply reduced after privacy-preserving process and several attack models could not be resisted by traditional algorithms, such as, semantic location attacks and maximum moving speed attacks, a trajectory privacy-preserving algorithm based on semantic location preservation under road network constraints, called k-CS (k-Connected Sub-graph) algorithm, was proposed. Firstly, two attack models in road network space were proposed. Secondly, the privacy problem of semantic trajectory was defined as the k-CS anonymity problem, which was then proven NP-hard. Finally, an approximation algorithm was proposed to cluster nodes in the road network to construct anonymity zones, and semantic locations were replaced with the corresponding anonymity zones. Experiments were implemented to compare the proposed algorithm with the classical algorithm, called (k,δ)-anonymity. The experimental results show that, the k-CS algorithm performs better than (k,δ)-anonymity algorithm in data utility, query error and runtime. Specifically, k-CS algorithm reduces about 20% in information loss than (k,δ)-anonymity, and k-CS algorithm deceased about 10% in runtime than (k,δ)-anonymity algorithm.

Key words: road network, privacy-preserving, trajectory data, semantic location, clustering

摘要： 针对轨迹数据隐私保护算法数据可用性低及易受语义位置攻击和最大运行速度攻击等问题，提出了一种在路网环境中基于语义轨迹的隐私保护算法——k-CS算法。首先，提出了两种路网环境中针对轨迹数据的攻击模型；然后，将路网环境中基于语义轨迹的隐私问题定义为k-CS匿名问题，并证明了该问题是一个NP难问题；最后，提出了一种基于图上顶点聚类的近似算法将图上的顶点进行匿名，将语义位置由相应的匿名区域取代。实验对所提算法和轨迹隐私保护经典算法（k，δ）-anonymity进行了对比，实验结果表明：k-CS算法在数据可用性、查询误差率、运行时间等方面优于（k，δ）-anonymity算法；平均信息丢失率比（k，δ）-anonymity算法降低了20%左右；算法运行时间比（k，δ）-anonymity算法减少近10%。

关键词: 路网, 隐私保护, 轨迹数据, 语义位置, 聚类

CLC Number:

HUO Zheng, CUI Honglei, HE Ping. k-CS algorithm: trajectory data privacy-preserving based on semantic location protection[J]. Journal of Computer Applications, 2018, 38(1): 182-187.

霍峥, 崔洪雷, 贺萍. 基于语义位置保护的轨迹隐私保护的k-CS算法[J]. 计算机应用, 2018, 38(1): 182-187.

References

[1] ZHENG Y. Trajectory data mining:an overview[J]. ACM Transactions on Intelligent Systems and Technology, 2015, 6(3):1-41.
[2] PARENT C, SPACCAPICTRA S, RENSO C, et al. Semantic trajectories modeling and analysis[J]. ACM Computing Surveys, 2013, 45(4):42.
[3] DAI J, HUA L. A method for the trajectory privacy protection based on the segmented fake trajectory under road networks[C]//Proceedings of the 2nd International Conference on Information Science and Control Engineering. Piscataway, NJ:IEEE, 2015:13-17.
[4] 赵婧,张渊,李兴华,等.基于轨迹频率抑制的轨迹隐私保护方法[J].计算机学报,2014,37(10):2096-2106.(ZHAO J, ZHANG Y, LI X H, et al. A trajectory privacy protection approach via trajectory frequency suppression[J]. Chinese Journal of Computers, 2014, 37(10):2096-2196.)
[5] HUO Z, MENG X, HU H, et al. You can walk alone:trajectory privacy-preserving through significant stays protection[C]//Proceedings of the 17th International Conference on Database Systems for Advanced Applications. Berlin:Springer, 2012:351-366.
[6] CAI Z F, YANG H X, SHUANH W, et al. A clustering-based privacy-preserving method for uncertain trajectory data[C]//Proceedings of the 2014 International Conference on Trust, Security and Privacy in Computing and Communications. Piscataway, NJ:IEEE, 2014:1-8.
[7] ABUL O. BONCHI F. NANNI M. Anonymization of moving objects databases by clustering and perturbation[J]. Information Systems, 2010, 35(8):884-910.
[8] 霍峥,孟小峰,黄毅.PrivateCheckIn:一种移动社交网络中的轨迹隐私保护方法[J].计算机学报,2013:36(4):716-726.(HUO Z, MENG X F, HUANG Y. PrivateCheckIn:trajectory privacy-preserving for check-in services in MSNS[J]. Chinese Journal of Computers, 2013, 36(4):716-726.)
[9] HUA J, GAO Y, ZHONG S. Differentially private publication of general time-serial trajectory data[C]//Proceedings of the 2015 IEEE Conference on Computer Communications. Piscataway, NJ:IEEE, 2015:549-557.
[10] PAN X, XU J, MENG X. Protecting location privacy against location-dependent attacks in mobile services[J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(8):1506-1519.
[11] CHOI T Y. A linear-time heuristic algorithm for k-way network partitioning[J]. Journal of the Korea Safety Management and Science, 2004, 7(8):1183-1194.
[12] YAROVOY R, BONCHI F, LAKSHMANAN L, et al. Anonymizing moving objects:how to hide a MOB in a crowd?[C]//Proceedings of the 12th International Conference on Extending Database Technology:Advances in Database Technology. New York:ACM, 2009:72-83.
[13] CHEN R, LI H, QIN K A, et al. Private spatial data aggregation in local setting[C]//Proceedings of the 32nd IEEE International Conference on Data Engineering. Piscataway, NJ:IEEE, 2016:289-300.
[14] SU S, TANG P, CHENG X, et al. Differentially private multi-party high-dimensional data publishing[C]//Proceedings of the 2016 International Conference on Data Engineering. Piscataway, NJ:IEEE, 2016:205-216.
[15] QIN Z, YANG Y, YU T, et al. Heavy hitter estimation over set-valued data with local differential privacy[C]//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. New York:ACM, 2016:192-203.
[16] 孟小峰,张啸剑.大数据隐私管理[J].计算机研究与发展,2016,52(2):265-281.(MENG X F, ZHANG X J. Big data privacy management[J]. Journal of Computer Research and Development, 2016, 52(2):265-281.)

k-CS algorithm: trajectory data privacy-preserving based on semantic location protection

基于语义位置保护的轨迹隐私保护的k-CS算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	CHEN Hengheng, NI Zhiwei, ZHU Xuhui, JIN Yuanyuan, CHEN Qian. Differential privacy high-dimensional data publishing method via clustering analysis [J]. Journal of Computer Applications, 2021, 41(9): 2578-2585.
[2]	ZENG Xiangyin, ZHENG Bochuan, LIU Dan. Detection of left and right railway tracks based on deep convolutional neural network and clustering [J]. Journal of Computer Applications, 2021, 41(8): 2324-2329.
[3]	ZHU Cheng, ZHAO Xiaoqi, ZHAO Liping, JIAO Yuhong, ZHU Yafei, CHENG Jianying, ZHOU Wei, TAN Ying. Classification of functional magnetic resonance imaging data based on semi-supervised feature selection by spectral clustering [J]. Journal of Computer Applications, 2021, 41(8): 2288-2293.
[4]	KANG Jun, HUANG Shan, DUAN Zongtao, LI Yixiu. Review of spatio-temporal trajectory sequence pattern mining methods [J]. Journal of Computer Applications, 2021, 41(8): 2379-2385.
[5]	DAI Yanran, DAI Guoqing, YUAN Yubo. Multi-face foreground extraction method based on skin color learning [J]. Journal of Computer Applications, 2021, 41(6): 1659-1666.
[6]	WANG Jiarui, TAN Guoping, ZHOU Siyuan. Clustered wireless federated learning algorithm in high-speed internet of vehicles scenes [J]. Journal of Computer Applications, 2021, 41(6): 1546-1550.
[7]	MA Jianhong, CAO Wenbin, LIU Yuangang, XIA Shuang. Patent clustering method based on functional effect [J]. Journal of Computer Applications, 2021, 41(5): 1361-1366.
[8]	LI Guorong, YE Jimin, ZHEN Yuanting. Time series clustering based on new robust similarity measure [J]. Journal of Computer Applications, 2021, 41(5): 1343-1347.
[9]	WANG Zhihe, CHANG Xiaoqing, DU Hui. Adaptive affinity propagation clustering algorithm based on universal gravitation [J]. Journal of Computer Applications, 2021, 41(5): 1337-1342.
[10]	LONG Chaoqi, JIANG Yu, XIE Yu. Improved wavelet clustering algorithm based on peak grid [J]. Journal of Computer Applications, 2021, 41(4): 1122-1127.
[11]	LI Xingfeng, HUANG Yuqing, REN Zhenwen, LI Yihong. Robust multi-view clustering algorithm based on adaptive neighborhood [J]. Journal of Computer Applications, 2021, 41(4): 1093-1099.
[12]	GUO Jia, HAN Litao, SUN Xianlong, ZHOU Lijuan. Comparative density peaks clustering algorithm with automatic determination of clustering center [J]. Journal of Computer Applications, 2021, 41(3): 738-744.
[13]	LYU Jia, XIAN Yan. Co-training algorithm combining improved density peak clustering and shared subspace [J]. Journal of Computer Applications, 2021, 41(3): 686-693.
[14]	ZOU Zhiwen, QIN Cheng. Method of dynamically constructing spatial topic R-tree based on k-means++ [J]. Journal of Computer Applications, 2021, 41(3): 733-737.
[15]	YUAN Qianqian, DENG Hongmin, WANG Xiaohang. Citrus disease and insect pest area segmentation based on superpixel fast fuzzy C-means clustering and support vector machine [J]. Journal of Computer Applications, 2021, 41(2): 563-570.