With the advancement of information technology, the value of data has further emerged. Trajectory data, being a type of massive data, has emerged as a valuable asset in enterprises and a driving force for innovation.However, privacy issues are also increasingly prominent. As a result, developing effective methods for protecting the privacy of trajectory data has become a research hotspot. However, most existing methods ignore temporal attributes and spatial distribution characteristics of trajectory data, resulting in loss of important information and reduced efficiency. To improve on the method, a new differentially private trajectory-data publishing algorithm,differentially private trajectory-data publishing based on generalization and probability(TPGP), is proposed in this work. The algorithm has three stages and generates a synthetic trajectory dataset. The first stage pre-processes trajectories, by performing time splitting and Hilbert space partitioning on the compressed trajectory data, without ignoring the time attribute. In the second stage, Laplace noise is added to obtain two key pieces of statistical information: the noisy counts of generalized trajectory and the noisy Markov transition probability with time attribute. The third stage generates and releases synthetic trajectories using the two pieces of statistical information obtained in the second stage. Experimental results indicate that the proposed TPGP scheme has significant advantages over existing methods in terms of ensuring data privacy while improving data utility.
[1] NERGIZ M E, ATZORI M, SAYGIN Y. Towards trajectory anonymization: A generalization-based approach [C]// SIGSPATIAL ACM GIS 2008 International Workshop on Security and Privacy in GIS and LBS. Irvine: ACM, 2008: 52-61.
[2] CHEN R, FUNG B C M, MOHAMMED N, et al. Privacy-preserving trajectory data publishing by local suppression [J]. Information Sciences, 2013, 231: 83-97.
[3] LUPER D, CAMERON D, MILLER J, et al. Spatial and temporal target association through semantic analysis and GPS data mining [C]// 2007 International Conference on Information & Knowledge Engineering. LasVegas: CSREA Press, 2007: 251-257.
[4] DWORK C. Differential privacy [M]// Automata, languages and programming. Berlin, Heidelberg: Springer, 2006: 1-12.
[5] CORMODE G, PROCOPIUC C, SRIVASTAVA D, et al. Differentially private spatial decompositions [C]//2012 IEEE 28th International Conference on Data Engineering. Arlington: IEEE, 2012: 20-31.
[6] ANDRÉS M E, BORDENABE N E, CHATZIKOKOLAKIS K, et al. Geo-indistinguishability: Differential privacy for location-based systems [C]// 2013 ACM SIGSAC Conference on Computer & Communications Security. Berlin: ACM, 2013: 901-914.
[7] CHATZIKOKOLAKIS K, PALAMIDESSI C, STRONATI M. A predictive differentially-private mechanism for mobility traces [M]// Privacy enhancing technologies. Cham: Springer, 2014: 21-41.
[8] HUA J Y, GAO Y, ZHONG S. Differentially private publication of general time-serial trajectory data [C]//2015 IEEE Conference on Computer Communications. Hong Kong: IEEE, 2015: 549-557.
[9] LI M, ZHU L H, ZHANG Z J, et al. Achieving differential privacy of trajectory data publishing in participatory sensing [J]. Information Sciences, 2017, 400: 1-13.
[10] GURSOY M E, LIU L, TRUEX S, et al. Differentially private and utility preserving publication of trajectory data [J]. IEEE Transactions on Mobile Computing, 2019, 18(10): 2315-2329.
[11] CHEN R, FUNG B C M, DESAI B C, et al. Differentially private transit data publication: A case study on the Montreal transportation system [C]// 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Beijing: ACM, 2012: 213-221.
[12] ABUL O, BONCHI F, NANNI M. Never walk alone: Uncertainty for anonymity in moving objects databases [C]//2008 IEEE 24th International Conference on Data Engineering. Cancun: IEEE, 2008: 376-385.
[13] DOMINGO-FERRER J, TRUJILLO-RASUA R. Microaggregation- and permutation-based anonymization of movement data [J]. Information Sciences, 2012, 208: 55-80.
[14] TRUJILLO-RASUA R, DOMINGO-FERRER J. On the privacy offered by (k, δ)-anonymity [J]. Information Systems, 2013, 38(4): 491-494.
[15] YAROVOY R, BONCHI F, LAKSHMANAN L V S, et al. Anonymizing moving objects: How to hide a MOB in a crowd? [C]// 12th International Conference on Extending Database Technology: Advances in Database Technology. Saint Petersburg: ACM, 2009: 72-83.
[16] PALANISAMY B, LIU L. Attack-resilient mix-zones over road networks: Architecture and algorithms [J]. IEEE Transactions on Mobile Computing, 2015, 14(3): 495-508.
[17] POULIS G, SKIADOPOULOS S, LOUKIDES G, et al. Apriori-based algorithms for k^ m-anonymizing trajectory data [J]. Transactions on Data Privacy, 2014, 7(2): 165-194.
[18] DWORK C, MCSHERRY F, NISSIM K, et al. Calibrating noise to sensitivity in private data analysis [M]//Theory of cryptography. Berlin, Heidelberg: Springer, 2006: 265-284.
[19] SHOKRI R, THEODORAKOPOULOS G, LE BOUDEC J Y, et al. Quantifying location privacy [C]//2011 IEEE Symposium on Security and Privacy. Oakland: IEEE, 2011: 247-262.
[20] SHOKRI R, THEODORAKOPOULOS G, TRONCOSO C, et al. Protecting location privacy: Optimal strategy against localization attacks [C]// 2012 ACM Conference on Computer and Communications Security. Raleigh: ACM, 2012: 617-627.
[21] TIAN J F, ZHU Q. A differential privacy trajectory data storage and publishing scheme based on radix tree [J]. Concurrency and Computation: Practice and Experience, 2023, 35(22): e7731.
[22] CHEN R, ACS G, CASTELLUCCIA C. Differentially private sequential data publication via variable-length n-grams [C]// 2012 ACM Conference on Computer and Communications Security. Raleigh: ACM, 2012: 638-649.
[23] XIAO Y H, XIONG L. Protecting locations with differential privacy under temporal correlations [C]// 22nd ACM SIGSAC Conference on Computer and Communications Security. Denver: ACM, 2015: 1298-1309.
[24] MA T H, SONG F G. A trajectory privacy protection method based on random sampling differential privacy [J]. ISPRS International Journal of Geo-Information, 2021, 10(7): 454.
[25] ZHAO Y X, WU W Q, DI C F. Release of trajectory data based on space segmentation using differential privacy [C]//2021 IEEE 20th International Conference on Trust, Security and Privacy in Computing and Communications. Shenyang: IEEE, 2021: 1246-1253.
[26] LI S B, QI Z Y, LI Q X. Vehicle trajectory data publishing mechanism based on differential privacy [C]//2021 China Automation Congress. Beijing: IEEE, 2021: 5373-5378.
[27] YU Y K, ZHU H, XIE M Y. CTP: Correlated trajectory publication with differential privacy [C]//2021 IEEE 6th International Conference on Computer and Communication Systems. Chengdu: IEEE, 2021: 128-133.
[28] YAO L, CHEN Z Y, HU H B, et al. Privacy preservation for trajectory publication based on differential privacy [J]. ACM Transactions on Intelligent Systems and Technology, 2022, 13(3): 1-21.
[29] SUN X Y, YE Q Q, HU H B, et al. PUTS: Privacy-preserving and utility-enhancing framework for trajectory synthesization [J]. IEEE Transactions on Knowledge and Data Engineering, 2024, 36(1): 296-310.
[30] MCSHERRY F, TALWAR K. Mechanism design via differential privacy [C]//48th Annual IEEE Symposium on Foundations of Computer Science. Providence: IEEE, 2007: 94-103.
[31] MCSHERRY F D. Privacy integrated queries: An extensible platform for privacy-preserving data analysis [C]// 2009 ACM SIGMOD International Conference on Management of Data. Providence: ACM, 2009: 19-30.
[32] BARRON A, RISSANEN J, YU B. The minimum description length principle in coding and modeling [J]. IEEE Transactions on Information Theory, 1998, 44(6): 2743-2760.
[33] HAY M, RASTOGI V, MIKLAU G, et al. Boosting the accuracy of differentially-private histograms through consistency [DB/OL]. (2009-04-06). https://arxiv.org/abs/0904.0942
[34] YUAN J, ZHENG Y, XIE X, et al. Driving with knowledge from the physical world [C]// 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Diego: ACM, 2011: 316-324.
[35] YUAN J, ZHENG Y, ZHANG C Y, et al. T-drive: Driving directions based on taxi trajectories [C]// 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. San Jose: ACM, 2010: 99-108.
