Differential Privacy Trajectory Protection Model Based on Personalized Spatiotemporal Clustering

doi:10.3969/j.issn.1671-1122.2024.01.008

Abstract

Abstract:

With the proliferation of location-aware devices, trajectory data has found widespread applications in real-life scenarios. However, trajectory data is often associated with sensitive labels, and improperly sharing or disclosing such data can pose privacy threats to users, with varying levels of sensitivity among different datasets. To address this issue, a differential privacy trajectory protection model based on personalized spatiotemporal clustering was proposed. Firstly, in response to the vast amount of temporal data in trajectories and the need for privacy protection, the fuzzy clustering means algorithm (FCM) was proposed. Secondly, during the spatial segmentation process, clustering was performed based on density, and personalized adjustments were made to allocate privacy budgets, thereby enhancing data utility. In the trajectory synthesis phase, a comparison was made with real trajectory data to select trajectories that were more representative. Finally, the Laplace mechanism was introduced in the release phase to protect the privacy of trajectory counts. To validate the achievements of the model in terms of trajectory utility and privacy protection, comparisons were made with various models in four stages. The experimental results indicate a 15.45% improvement in data utility for the proposed model and, under the same privacy budget, enhances privacy protection strength by at least 35.62%.

Key words: personalized budget allocation, differential privacy, spatiotemporal clustering, trajectory privacy, trajectory publication

CLC Number:

TP309

YIN Chunyong, JIANG Yiyang. Differential Privacy Trajectory Protection Model Based on Personalized Spatiotemporal Clustering[J]. Netinfo Security, 2024, 24(1): 80-92.

Figures/Tables 10

References 32

[1]	ZHAO Xiaodong, PI Dechang, CHEN Junfu. Novel Trajectory Privacy-Preserving Method Based on Clustering Using Differential Privacy[J]. Expert Systems with Applications, 2020, 149: 3305-3317.
[2]	WU Lei, QIN Chengyi, XU Zihui, et al. TCPP: Achieving Privacy-Preserving Trajectory Correlation with Differential Privacy[J]. IEEE Transactions on Information Forensics and Security, 2023, 18: 4006-4020. doi: 10.1109/TIFS.2023.3290486 URL
[3]	GAZDAG A, LESTYAN S, REMELI M, et al. Privacy Pitfalls of Releasing In-Vehicle Network Data[EB/OL]. (2022-12-09) [2023-10-20]. https://doi.org/10.1016/j.vehcom.2022.100565.
[4]	MA Tinghuai, DENG Qian, RONG Huan, et al. A Privacy-Preserving Trajectory Data Synthesis Framework Based on Differential Privacy[EB/OL]. (2023-07-25) [2023-10-20]. https://doi.org/10.1016/j.jisa.2023.103550.
[5]	ZHAO Jia, GAO Ta, ZHANG Jiancheng. Method of Local Differential Privacy Method for High-Dimensional Data Based on Improved Bayesian Network[J]. Netinfo Security, 2023, 23(2): 19-25.
	赵佳, 高塔, 张建成. 基于改进贝叶斯网络的高维数据本地差分隐私方法[J]. 信息网络安全, 2023, 23(2): 19-25.
[6]	SWEENEY L. K-Anonymity: A Model for Protecting Privacy[J]. International Journal of Uncertainty Fuzziness and Knowledge-Based Systems, 2002, 10(5): 557-570. doi: 10.1142/S0218488502001648 URL
[7]	SU Bing, HUANG Jiaxuan, MIAO Kelei, et al. K-Anonymity Privacy Protection Algorithm for Multi-Dimensional Data against Skewness and Similarity Attacks[J]. Sensors, 2023, 23(3): 56-68. doi: 10.3390/s23010056 URL
[8]	DWORK C. Differential Privacy[C]// Springer. Proccedings of the 33rd International Colloquium on Automata, Languages and Programming. Heirdelberg: Springer, 2006: 1-12.
[9]	DWORK C. Differential Privacy: A Survey of Results[C]// Springer. International Conference on Theory and Applications of Models of Computation. Heirdelberg: Springer, 2008: 1-19.
[10]	MCSHERRY F, TALWAR K. Mechanism Design via Differential Privacy[C]// IEEE. 48th Annual IEEE Symposium on Foundations of Computer Science. New York: IEEE, 2007: 94-103.
[11]	MCSHERRY F, MIRONOV I. Differentially Private Recommender Systems: Building Privacy into the Netflix Prize Contenders[C]// ACM. 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2009: 627-636.
[12]	SUN Liping, BAO Shuting, CI Shang, et al. Differential Privacy-Preserving Density Peaks Clustering Based on Shared Near Neighbors Similarity[J]. IEEE Access, 2019, 7: 89427-89440. doi: 10.1109/ACCESS.2019.2927308
[13]	PARK J, LEE D H. Parallelly Running K-Nearest Neighbor Classification over Semantically Secure Encrypted Data in Outsourced Environments[J]. IEEE Access, 2020, 8: 64617-64633. doi: 10.1109/Access.6287639 URL
[14]	YAO Lin, CHEN Zhenyu, HU Haibo, et al. Privacy Preservation for Trajectory Publication Based on Differential Privacy[J]. ACM Transactions on Intelligent Systems and Technology, 2022, 13(3): 82-91.
[15]	GU Zhen, ZHANG Guoyin. Trajectory Data Publication Based on Differential Privacy[J]. International Journal of Information Security and Privacy (IJISP), 2023, 17(1): 1-15.
[16]	LIU Qi, YU Juan, HAN Jianmin, et al. Differentially Private and Utility-Aware Publication of Trajectory Data[EB/OL]. (2021-04-28) [2023-10-20]. https://doi.org/10.1016/j.eswa.2021.115120.
[17]	GENG Quan, KAIROUZ P, OH S, et al. The Staircase Mechanism in Differential Privacy[J]. IEEE Journal of Selected Topics in Signal Processing, 2015, 9(7): 1176-1184. doi: 10.1109/JSTSP.2015.2425831 URL
[18]	CAI Sujin, LYU Xin, LI Xin, et al. A Trajectory Released Scheme for the Internet of Vehicles Based on Differential Privacy[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(9): 16534-16547. doi: 10.1109/TITS.2021.3130978 URL
[19]	LI Hongtao, WANG Yue, GUO Feng, et al. Differential Privacy Location Protection Method Based on the Markov Model[EB/OL]. (2021-07-01) [2023-10-20]. https://doi.org/10.1155/2021/4696455.
[20]	ZHANG Yaling, LIU Na, WANG Shangping. A Differential Privacy Protecting K-Means Clustering Algorithm Based on Contour Coefficients[J]. PLOS ONE, 2018, 13(11): 58-70.
[21]	DING Xiaofeng, YANG Wanlu, CHOO K K R, et al. Privacy Preserving Similarity Joins Using MapReduce[J]. Information Sciences, 2019, 493: 20-33. doi: 10.1016/j.ins.2019.03.035
[22]	GURSOY M E, LIU Ling, TRUEX S, et al. Differentially Private and Utility Preserving Publication of Trajectory Data[J]. IEEE Transactions on Mobile Computing, 2019, 18(10): 2315-2329. doi: 10.1109/TMC.7755 URL
[23]	CHEN Si, FU Anmin, SHEN Jian, et al. RNN-DP: A New Differential Privacy Scheme Base on Recurrent Neural Network for Dynamic Trajectory Privacy Protection[J]. Journal of Network and Computer Applications, 2020, 168: 1036-1048.
[24]	ZHANG Ziming, XU Xiaolong, XIAO Fu. LGAN-DP: A Novel Differential Private Publication Mechanism of Trajectory Data[J]. Future Generation Computer Systems-The International Journal of Escience, 2023, 141: 692-703.
[25]	LI Youru, ZHU Zhenfeng, KONG Deqiang, et al. EA-LSTM: Evolutionary Attention-Based LSTM for Time Series Prediction[J]. Knowledge-Based Systems, 2019, 181: 265-277.
[26]	CHENG Wenqing, WEN Ruxue, HUANG Haojun, et al. OPTDP: Towards Optimal Personalized Trajectory Differential Privacy for Trajectory Data Publishing[J]. Neurocomputing, 2022, 472: 201-211. doi: 10.1016/j.neucom.2021.04.137 URL
[27]	LI Jiachun, CHEN Guoqian. A Personalized Trajectory Privacy Protection Method[J]. Computers & Security, 2021, 108: 131-142.
[28]	Bezdek J C. Pattern Recognition with Fuzzy Objective Function Algorithms[M]. Heirdelberg: Springer Science & Business Media, 2013.
[29]	YUAN Jing, ZHENG Yu, ZHANG Chengyang, et al. T-Drive: Driving Directions Based on Taxi Trajectories[C]// ACM. 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2010: 99-108.
[30]	YUAN Jing, ZHENG Yu, XIE Xing, et al. Driving with Knowledge from the Physical World[C]// ACM. 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2011: 316-324.
[31]	HUA Jingyu, GAO Yue, ZHONG Sheng. Differentially Private Publication of General Time-Serial Trajectory Data[C]// IEEE. 2015 IEEE Conference on Computer Communications. New York: IEEE, 2015: 549-557.
[32]	CHEN Si, FU Anmin, SU Mang, et al. Trajectory Privacy Protection Scheme Based on Differential Privacy[J]. Journal on Communications, 2021, 42(9): 54-64. doi: 10.11959/j.issn.1000-436x.2021168
	陈思, 付安民, 苏铓, 等. 基于差分隐私的轨迹隐私保护方案[J]. 通信学报, 2021, 42(9): 54-64. doi: 10.11959/j.issn.1000-436x.2021168

参数	含义
$\tilde{T}$	原始轨迹
D	时间概化后的数据集
DG	时空处理后的数据集
t	时刻
p	区域L中的分组数
P	分区中组的集合
tc	真实轨迹数量
la	Laplace噪声
rc	发布的轨迹数据集

新轨迹数据集	与新轨迹相似的原始轨迹	真实记录数	是否异常
${{\tilde{l}}_{13}}\to {{\tilde{l}}_{21}}\to {{\tilde{l}}_{32}}$	${{T}_{2}},{{T}_{5}},{{T}_{7}}$	2	否
${{\tilde{l}}_{13}}\to {{\tilde{l}}_{23}}\to {{\tilde{l}}_{32}}$	${{T}_{7}}$	1	否
${{\tilde{l}}_{13}}\to {{\tilde{l}}_{23}}\to {{\tilde{l}}_{33}}$	—	0	是
${{\tilde{l}}_{12}}\to {{\tilde{l}}_{21}}\to {{\tilde{l}}_{33}}$	${{T}_{3}}$	2	否
${{\tilde{l}}_{11}}\to {{\tilde{l}}_{23}}\to {{\tilde{l}}_{31}}$	${{T}_{1}}$	2	否
${{\tilde{l}}_{11}}\to {{\tilde{l}}_{23}}\to {{\tilde{l}}_{32}}$	—	0	是
${{\tilde{l}}_{13}}\to {{\tilde{l}}_{22}}\to {{\tilde{l}}_{32}}$	${{T}_{4}},{{T}_{6}}$	4	否
${{\tilde{l}}_{11}}\to {{\tilde{l}}_{21}}\to {{\tilde{l}}_{33}}$	—	0	是