Journal Home > Volume 29 , Issue 2
Tsinghua Science and Technology 2024, 29(2): 617-633 https://doi.org/10.26599/TST.2023.9010072
Open Access | Issue | Published: 22 September 2023

A Local Differential Privacy Trajectory Protection Method Based on Temporal and Spatial Restrictions for Staying Detection

Show Author's Information Weiqi Zhang1,  Zhenzhen Xie2,  Akshita Maradapu Vera Venkata Sai3,  Qasim Zia3,  Zaobo He4,  Guisheng Yin1( )
College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China
School of Computer Science and Technology, Shandong University, Qingdao 266237, China
Department of Computer Science, Georgia State University, Atlanta, GA 30303, USA
College of Information Science and Technology, Jinan University, Guangzhou 510632, China
Keywords:
trajectory data, local-differential privacy, stay points detection, areas of interest, temporal-spatial clustering
Cite this article:
Zhang W, Xie Z, Sai AMVV, et al. A Local Differential Privacy Trajectory Protection Method Based on Temporal and Spatial Restrictions for Staying Detection. Tsinghua Science and Technology, 2024, 29(2): 617-633. https://doi.org/10.26599/TST.2023.9010072
Download citation
EndNote(RIS)
BibTeX

80

Views

8

Downloads

Citations

0

Crossref

0

WoS

0

Scopus

0

CSCD

Abstract Full text About this article

The widespread availability of GPS has opened up a whole new market that provides a plethora of location-based services. Location-based social networks have become very popular as they provide end users like us with several such services utilizing GPS through our devices. However, when users utilize these services, they inevitably expose personal information such as their ID and sensitive location to the servers. Due to untrustworthy servers and malicious attackers with colossal background knowledge, users’ personal information is at risk on these servers. Unfortunately, many privacy-preserving solutions for protecting trajectories have significantly decreased utility after deployment. We have come up with a new trajectory privacy protection solution that contraposes the area of interest for users. Firstly, Staying Points Detection Method based on Temporal-Spatial Restrictions (SPDM-TSR) is an interest area mining method based on temporal-spatial restrictions, which can clearly distinguish between staying and moving points. Additionally, our privacy protection mechanism focuses on the user’s areas of interest rather than the entire trajectory. Furthermore, our proposed mechanism does not rely on third-party service providers and the attackers’ background knowledge settings. We test our models on real datasets, and the results indicate that our proposed algorithm can provide a high standard privacy guarantee as well as data availability.


menu
Abstract
Full text
Outline
About this article

A Local Differential Privacy Trajectory Protection Method Based on Temporal and Spatial Restrictions for Staying Detection

Show Author's information Weiqi Zhang1, Zhenzhen Xie2, Akshita Maradapu Vera Venkata Sai3, Qasim Zia3, Zaobo He4, Guisheng Yin1( )
College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China
School of Computer Science and Technology, Shandong University, Qingdao 266237, China
Department of Computer Science, Georgia State University, Atlanta, GA 30303, USA
College of Information Science and Technology, Jinan University, Guangzhou 510632, China

Abstract

The widespread availability of GPS has opened up a whole new market that provides a plethora of location-based services. Location-based social networks have become very popular as they provide end users like us with several such services utilizing GPS through our devices. However, when users utilize these services, they inevitably expose personal information such as their ID and sensitive location to the servers. Due to untrustworthy servers and malicious attackers with colossal background knowledge, users’ personal information is at risk on these servers. Unfortunately, many privacy-preserving solutions for protecting trajectories have significantly decreased utility after deployment. We have come up with a new trajectory privacy protection solution that contraposes the area of interest for users. Firstly, Staying Points Detection Method based on Temporal-Spatial Restrictions (SPDM-TSR) is an interest area mining method based on temporal-spatial restrictions, which can clearly distinguish between staying and moving points. Additionally, our privacy protection mechanism focuses on the user’s areas of interest rather than the entire trajectory. Furthermore, our proposed mechanism does not rely on third-party service providers and the attackers’ background knowledge settings. We test our models on real datasets, and the results indicate that our proposed algorithm can provide a high standard privacy guarantee as well as data availability.

Keywords: trajectory data, local-differential privacy, stay points detection, areas of interest, temporal-spatial clustering

References(40)

[1]
Y. Huang, Y. J. Li, and Z. Cai, Security and privacy in metaverse: A comprehensive survey, Big Data Mining and Analytics, vol. 6, no. 2, pp. 234–247, 2023.
DOI Google Scholar
[2]
O. Abul, F. Bonchi, and M. Nanni, Never walk alone: Uncertainty for anonymity in moving objects databases, in Proc. 2008 IEEE 24th Int. Conf. Data Engineering, Cancun, Mexico, 2008, pp. 376–385.
DOI Google Scholar
[3]
P. Samarati and L. Sweeney, Generalizing data to provide anonymity when disclosing information, in Proc.17th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Seattle, WA, USA, 1998, pp. 188–201.
DOI Google Scholar
[4]
O. Abul, F. Bonchi, and M. Nanni, Anonymization of moving objects databases by clustering and perturbation, Inf. Syst., vol. 35, no. 8, pp. 884–910, 2010.
DOI Google Scholar
[5]
N. Mohammed, B. C. M. Fung, and M. Debbabi, Walking in the crowd: Anonymizing trajectory data for pattern analysis, in Proc. 18th ACM Conf. Information and Knowledge Management, Hong Kong, China, 2009, pp. 1441–1444.
DOI Google Scholar
[6]
R. Chen, B. C. M. Fung, N. Mohammed, B. C. Desai, and K. Wang, Privacy-preserving trajectory data publishing by local suppression, Inf. Sci., vol. 231, pp. 83–97, 2013.
DOI Google Scholar
[7]
S. Papadopoulos, S. Bakiras, and D. Papadias, Nearest neighbor search with strong location privacy, Proc. VLDB Endow., vol. 3, nos. 1&2, pp. 619–629, 2010.
DOI Google Scholar
[8]
S. Yang, C. Ma, and C. Zhou, SL-Cloak: PIR technology based stochastic location cloaking method, in Proc. Int. Conf. Computer, Network Security and Communication Engineering, Shenzhen, China, 2014, pp. 395–399.
Google Scholar
[9]
J. Freudiger, M. Raya, and M. Feleghhazi, Mix-zones for location privacy in vehicular networks, presented at WiN-ITS, Vancouver, Canada, 2007.
Google Scholar
[10]
I. Memon, H. T. Mirza, Q. A. Arain, and H. Memon, Multiple mix zones de-correlation trajectory privacy model for road network, Telecommun. Syst., vol. 70, no. 4, pp. 557–582, 2019.
DOI Google Scholar
[11]
C. Dwork, Differential privacy in new settings, in Proc. Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, Austin, TX, USA, 2010, pp.174–183.
DOI Google Scholar
[12]
K. Zhang, Z. Tian, Z. Cai, and D. Seo, Link-privacy preserving graph embedding data publication with adversarial learning, Tsinghua Science and Technology, vol. 27, no. 2, pp. 244–256, 2022.
DOI Google Scholar
[13]
R. Chen, B. C. M. Fung, and B. C. Desai, Differentially private trajectory data publication, arXiv preprint arXiv: 1112.2020, 2011.
Google Scholar
[14]
Z. Cai, X. Zheng, J. Wang, and Z. He, Private data trading towards range counting queries in Internet of Things, IEEE Trans. Mob. Comput., vol. 22, no. 8, pp. 4881–4897, 2023.
DOI Google Scholar
[15]
Z. Cai and Z. He, Trading private range counting over big IoT data, in Proc. 2019 IEEE 39th Int. Conf. Distributed Computing Systems (ICDCS), Dallas, TX, USA, 2019, pp. 144–153.
DOI Google Scholar
[16]
Z. Cai and X. Zheng, A private and efficient mechanism for data uploading in smart cyber-physical systems, IEEE Trans. Netw. Sci. Eng., vol. 7, no. 2, pp. 766–775, 2020.
DOI Google Scholar
[17]
X. Zheng and Z. Cai, Privacy-preserved data sharing towards multiple parties in industrial IoTs, IEEE J. Sel. Areas Commun., vol. 38, no. 5, pp. 968–979, 2020.
DOI Google Scholar
[18]
R. Chen, B. C. M. Fung, B. C. Desai, and N. M. Sossou, Differentially private transit data publication: A case study on the Montreal transportation system, in Proc. 18th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, Beijing, China, 2012, pp. 213–221.
DOI Google Scholar
[19]
S. S. Ho and S. Ruan, Differential privacy for location pattern mining, in Proc. 4th ACM SIGSPATIAL Int. Workshop on Security and Privacy in GIS and LBS, Chicago, IL, USA, 2011, pp. 17–24.
Google Scholar
[20]
Y. Xiao and L. Xiong, Protecting locations with differential privacy under temporal correlations, in Proc. 22nd ACM SIGSAC Conf. Computer and Communications Security, Denver, CO, USA, 2015, pp. 1298–1309.
DOI Google Scholar
[21]
L. Ou, Z. Qin, S. Liao, Y. Hong, and X. Jia, Releasing correlated trajectories: Towards high utility and optimal differential privacy, IEEE Trans. Dependable Secure Comput., vol. 17, no. 5, pp. 1109–1123, 2020.
DOI Google Scholar
[22]
Y. Wang, M. Li, S. Luo, Y. Xin, H. Zhu, Y. Chen, G. Yang, and Y. Yang, LRM: A location recombination mechanism for achieving trajectory k-anonymity privacy protection, IEEE Access, vol. 7, pp. 182886–182905, 2019.
DOI Google Scholar
[23]
W. Zhang, G. Yin, Y. Sha, and J. Yang, Protecting the moving user’s locations by combining differential privacy and k-anonymity under temporal correlations in wireless networks, Wirel. Commun. Mob. Comput., vol. 2021, pp. 1–12, 2021.
DOI Google Scholar
[24]
Z. Hu, J. Yang, and J. Zhang, Trajectory privacy protection method based on the time interval divided, Comput. Secur., vol. 77, pp. 488–499, 2018.
DOI Google Scholar
[25]
L. Gong, H. Sato, T. Yamamoto, T. Miwa, and T. Morikawa, Identification of activity stop locations in GPS trajectories by density-based clustering method combined with support vector machines, J. Mod. Transp., vol. 23, pp. 202–213, 2015.
DOI Google Scholar
[26]
T. Luo, X. Zheng, G. Xu, K. Fu, and W. Ren, An improved DBSCAN algorithm to detect stops in individual trajectories, ISPRS Int. J. Geo Inf., vol. 6, no. 3, p. 63, 2017.
DOI Google Scholar
[27]
L. Bermingham and I. Lee, A probabilistic stop and move classifier for noisy GPS trajectories, Data Min. Knowl. Discov., vol. 32, no. 6, pp. 1634–1662, 2018.
DOI Google Scholar
[28]
P. Kairouz, S. Oh, and P. Viswanath, Extremal mechanisms for local differential privacy, in Proc. 27th Int. Conf. Neural Information Processing Systems, Montreal, Canada, 2014, pp. 2879–2887.
Google Scholar
[29]
W. Y. Gan, D. Y. Li, and J. M. Wang, An hierarchical clustering method based on data fields, Acta Electron. Sin., vol. 35, no. 2, pp. 258–262, 2006.
Google Scholar
[30]
Z. Cai, Z. Xiong, H. Xu, P. Wang, W. Li, and Y. Pan, Generative adversarial networks: A survey toward private and secure applications, ACM Comput. Surv., vol. 54, no. 6, pp. 1–38, 2021.
DOI Google Scholar
[31]
Y. Zheng, L. Zhang, X. Xie, and W. Y. Ma, Mining interesting locations and travel sequences from GPS trajectories, in Proc. 18th Int. Conf. World Wide Web, Madrid, Spain, 2009, pp. 791–800.
DOI Google Scholar
[32]
Y. Zheng, Q. Li, Y. Chen, X. Xie, and W. Y. Ma, Understanding mobility based on GPS data, in Proc. 10th Int. Conf. Ubiquitous Computing, Seoul, Republic of Korea, 2008, pp. 312–321.
DOI Google Scholar
[33]
Y. Zheng, X. Xie, and W. Y. Ma, GeoLife: A collaborative social networking service among user, location and trajectory, IEEE Data Eng. Bull., vol. 33, pp.32–39, 2010.
Google Scholar
[34]
A. T. Palma, V. Bogorny, B. Kuijpers, and L. O. Alvares, A clustering-based approach for discovering interesting places in trajectories, in Proc. 2008 ACM Symp. on Applied computing, Fortaleza, Brazil, 2008, pp. 863–868.
DOI Google Scholar
[35]
K. Gu, L. Yang, Y. Liu, and N. Liao, Trajectory data privacy protection based on differential privacy mechanism, in Proc. 2017 2nd Int. Conf. Reliability Engineering (ICRE 2017), Milan, Italy, 2017, pp. 122–127.
Google Scholar
[36]
Z. Cai, Z. He, X. Guan, and Y. Li, Collective data-sanitization for preventing sensitive information inference attacks in social networks, IEEE Trans. Dependable Secure Comput., vol. 15, no. 4, pp. 577–590, 2018.
Google Scholar
[37]
J. He, B. Gong, J. Yang, H. Wang, P. Xu, and T. Xing, ASCFL: Accurate and speedy semi-supervised clustering federated learning, Tsinghua Science and Technology, vol. 28, no. 5, pp. 823–837, 2023.
DOI Google Scholar
[38]
M. Yang, L. Huang, C. Tang, K-means clustering with local distance privacy, Big Data Mining and Analytics, .
DOI Google Scholar
[39]
K. Jiang, D. Shao, S. Bressan, T. Kister, and K. L. Tan, Publishing trajectories with differential privacy guarantees, in Proc. 25th Int. Conf. Scientific and Statistical Database Management, Baltimore, MD, USA, 2013, pp. 1–12.
DOI Google Scholar
[40]
P. Chen, J. Gu, D. Zhu, and F. Shao, A dynamic time warping based algorithm for trajectory matching in LBS, International Journal of Database Theory and Application, vol. 6, no. 3, pp. 39–48, 2013.
Google Scholar
Publication history
Copyright
Rights and permissions

Publication history

Received: 21 June 2023
Revised: 12 July 2023
Accepted: 15 July 2023
Published: 22 September 2023
Issue date: April 2024

Copyright

© The author(s) 2024.

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return