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

doi:10.11772/j.issn.1001-9081.2017071676

计算机应用 ›› 2018, Vol. 38 ›› Issue (1): 182-187.DOI: 10.11772/j.issn.1001-9081.2017071676

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

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

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

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

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).

摘要/Abstract

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

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

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算法[J]. 计算机应用, 2018, 38(1): 182-187.

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.

参考文献

[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算法

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	陈恒恒, 倪志伟, 朱旭辉, 金媛媛, 陈千. 基于聚类分析的差分隐私高维数据发布方法[J]. 计算机应用, 2021, 41(9): 2578-2585.
[2]	李卓, 宋子晖, 沈鑫, 陈昕. 边缘计算支持下的移动群智感知本地差分隐私保护机制[J]. 计算机应用, 2021, 41(9): 2678-2686.
[3]	祝承, 赵晓琦, 赵丽萍, 焦玉宏, 朱亚飞, 陈建英, 周伟, 谭颖. 基于谱聚类半监督特征选择的功能磁共振成像数据分类[J]. 计算机应用, 2021, 41(8): 2288-2293.
[4]	康军, 黄山, 段宗涛, 李宜修. 时空轨迹序列模式挖掘方法综述[J]. 计算机应用, 2021, 41(8): 2379-2385.
[5]	曾祥银, 郑伯川, 刘丹. 基于深度卷积神经网络和聚类的左右轨道线检测[J]. 计算机应用, 2021, 41(8): 2324-2329.
[6]	戴嫣然, 戴国庆, 袁玉波. 基于肤色学习的多人脸前景抽取方法[J]. 计算机应用, 2021, 41(6): 1659-1666.
[7]	马建红, 曹文斌, 刘元刚, 夏爽. 基于功效特征的专利聚类方法[J]. 计算机应用, 2021, 41(5): 1361-1366.
[8]	王治和, 常筱卿, 杜辉. 基于万有引力的自适应近邻传播聚类算法[J]. 计算机应用, 2021, 41(5): 1337-1342.
[9]	李国荣, 冶继民, 甄远婷. 基于新的鲁棒相似性度量的时间序列聚类[J]. 计算机应用, 2021, 41(5): 1343-1347.
[10]	秦静, 安雯, 季长清, 汪祖民. 无线体域网隐私保护机制研究综述[J]. 计算机应用, 2021, 41(4): 970-975.
[11]	李杏峰, 黄玉清, 任珍文, 李毅红. 基于自适应邻域的鲁棒多视图聚类算法[J]. 计算机应用, 2021, 41(4): 1093-1099.
[12]	龙超奇, 蒋瑜, 谢雨. 基于峰值网格改进的小波聚类算法[J]. 计算机应用, 2021, 41(4): 1122-1127.
[13]	刘向宇, 夏国平, 夏秀峰, 宗传玉, 朱睿, 李佳佳. 个性化时空数据隐私保护[J]. 计算机应用, 2021, 41(3): 643-650.
[14]	郭佳, 韩李涛, 孙宪龙, 周丽娟. 自动确定聚类中心的比较密度峰值聚类算法[J]. 计算机应用, 2021, 41(3): 738-744.
[15]	吕佳, 鲜焱. 结合改进密度峰值聚类和共享子空间的协同训练算法[J]. 计算机应用, 2021, 41(3): 686-693.