{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T04:19:28Z","timestamp":1769141968939,"version":"3.49.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2026,3,31]]},"abstract":"<jats:p>\n                    The increasing use of GPS-enabled devices has generated a large amount of trajectory data. These data offer us vital insights to understand the movements of individuals and populations, benefiting a broad range of applications from transportation planning to epidemic modeling. However, improper release of trajectory data is increasing concerns on individual privacy. Previous attempts either lack strong privacy guarantees, or fail to preserve sufficient basic characteristics of the original data. In this article, we propose DPTraj-PM, a method to synthesize trajectory dataset under the differential privacy (DP) framework while ensure high data utility. Based on the assumption that an individual's trajectory could be mainly determined by the initial trajectory segment (which depicts the starting point and the initial direction) and the next location point, DPTraj-PM discretizes the raw trajectories into neighboring cells, and models them by combining a prefix tree structure and an\n                    <jats:italic toggle=\"yes\">m<\/jats:italic>\n                    -order Markov process. After adding noise to the model under differential privacy, DPTraj-PM generates a synthetic dataset from the noisy model to enable a wider spectrum of data mining and modeling tasks. The output traces crafted by DPTraj-PM not only preserve the patterns and variability in individuals\u2019 mobility behaviors, but also protect individual privacy. Experiments on two real-world datasets demonstrate that DPTraj-PM substantially outperforms the state-of-the-art techniques in terms of data utility. Our code is available at\n                    <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"url\" xlink:href=\"https:\/\/github.com\/wnn5\/DP-PrefixTreeMarkov\">https:\/\/github.com\/wnn5\/DP-PrefixTreeMarkov<\/jats:ext-link>\n                    .\n                  <\/jats:p>","DOI":"10.1145\/3778164","type":"journal-article","created":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T11:51:15Z","timestamp":1764762675000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["DPTraj-PM: Differentially Private Trajectory Synthesis Using Prefix Tree and Markov Process"],"prefix":"10.1145","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6368-3545","authenticated-orcid":false,"given":"Nana","family":"Wang","sequence":"first","affiliation":[{"name":"School of Artificial Intelligence and Computer Science, Jiangsu Normal University","place":["Xuzhou, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4846-2015","authenticated-orcid":false,"given":"Mohan","family":"Kankanhalli","sequence":"additional","affiliation":[{"name":"School of Computing, National University of Singapore","place":["Singapore, Singapore"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,1,22]]},"reference":[{"key":"e_1_3_1_2_2","first-page":"496","volume-title":"Proceedings of the Privacy Enhancing Technologies","author":"Miranda-Pascual \u00c0lex","year":"2023","unstructured":"\u00c0lex Miranda-Pascual, Patricia Guerra-Balboa, Javier Parra-Arnau, Jordi Forn\u00e9, and Thorsten Strufe. 2023. SoK: Differentially private publication of trajectory data. In Proceedings of the Privacy Enhancing Technologies. 496\u2013516."},{"key":"e_1_3_1_3_2","first-page":"91","article-title":"Privacy in trajectory micro-data: A survey","volume":"13","author":"Fiore Marco","year":"2020","unstructured":"Marco Fiore, Panagiota Katsikouliy, Elli Zavouy, Mathieu Cunchey, Franc\u00b8oise Fessantz, Dominique L. Helloz, Ulrich M. Aivodjix, Baptiste Olivierz, Tony Quertierz, and Razvan Stanica. 2020. Privacy in trajectory micro-data: A survey. Transactions on Data Privacy 13, 2 (2020), 91\u2013149.","journal-title":"Transactions on Data Privacy"},{"issue":"1","key":"e_1_3_1_4_2","first-page":"1","article-title":"Unique in the crowd: The privacy bounds of human mobility","volume":"3","author":"de Montjoye Yves-Alexandre","year":"2013","unstructured":"Yves-Alexandre de Montjoye, Ce\u00b4sar A. Hidalgo, Michel Verleysen, and Vincent D. Blondel. 2013. Unique in the crowd: The privacy bounds of human mobility. Scientific Reports 3, 1 (2013), 1\u20135.","journal-title":"Scientific Reports"},{"issue":"1","key":"e_1_3_1_5_2","first-page":"1","article-title":"On the difficulty of achieving differential privacy in practice: User-level guarantees in aggregate location data","volume":"13","author":"Houssiau Florimond","year":"2022","unstructured":"Florimond Houssiau, Luc Rocher, and Yves-Alexandre de Montjoye. 2022. On the difficulty of achieving differential privacy in practice: User-level guarantees in aggregate location data. Nature Communications 13, 1 (2022), 1\u20133.","journal-title":"Nature Communications"},{"issue":"6","key":"e_1_3_1_6_2","first-page":"5577","article-title":"A survey and experimental study on privacy-preserving trajectory data publishing","volume":"35","author":"Jin Fengmei","year":"2022","unstructured":"Fengmei Jin, Wen Hua, Matteo Francia, Pingfu Chao, Maria E Orlowska, and Xiaofang Zhou. 2022. A survey and experimental study on privacy-preserving trajectory data publishing. IEEE Transactions on Knowledge and Data Engineering 35, 6 (2022), 5577\u20135596.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_3_1_7_2","doi-asserted-by":"crossref","first-page":"94","DOI":"10.23919\/ICACT48636.2020.9061335","volume-title":"Proceedings of the 2020 22nd International Conference on Advanced Communication Technology (ICACT)","author":"Shin Seungjae","year":"2020","unstructured":"Seungjae Shin, Hongseok Jeon, Chunglae Cho, Seunghyun Yoon, and Taeyeon Kim. 2020. User mobility synthesis based on generative adversarial networks: A survey. In Proceedings of the 2020 22nd International Conference on Advanced Communication Technology (ICACT). IEEE, 94--103."},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10462-023-10598-x"},{"key":"e_1_3_1_9_2","first-page":"376","volume-title":"Proceedings of the IEEE 24th International Conference on Data Engineering","author":"Abul Osman","year":"2008","unstructured":"Osman Abul, Francesco Bonchi, and Mirco Nanni. 2008. Never walk alone: Uncertainty for anonymity in moving objects databases. In Proceedings of the IEEE 24th International Conference on Data Engineering. IEEE, 376\u2013385."},{"issue":"1","key":"e_1_3_1_10_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3363449","article-title":"Privacy-and context-aware release of trajectory data","volume":"6","author":"Naghizade Elham","year":"2020","unstructured":"Naghizade, Elham, Lars Kulik, Egemen Tanin, and James Bailey. 2020. Privacy-and context-aware release of trajectory data. ACM Transactions on Spatial Algorithms and Systems (TSAS) 6, 1 (2020), 1--25.","journal-title":"ACM Transactions on Spatial Algorithms and Systems (TSAS)"},{"key":"e_1_3_1_11_2","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1109\/Trustcom.2015.417","volume-title":"Proceedings of the 2015 IEEE Trustcom\/BigDataSE\/ISPA","author":"Primault Vincent","year":"2015","unstructured":"Vincent Primault, Sonia Ben Mokhtar, C\u00e9dric Lauradoux, and Lionel Brunie. 2015. Time distortion anonymization for the publication of mobility data with high utility. In Proceedings of the 2015 IEEE Trustcom\/BigDataSE\/ISPA. IEEE, 539\u2013546."},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIFS.2019.2928205"},{"key":"e_1_3_1_13_2","first-page":"36","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","author":"Zhu Yuanshao","year":"2024","unstructured":"Yuanshao Zhu, Yongchao Ye, Shiyao Zhang, Xiangyu Zhao, and James J. Q. Yu. 2024. Difftraj: Generating GPS trajectory with diffusion probabilistic model. In Proceedings of the Advances in Neural Information Processing Systems. 36."},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0342-x"},{"key":"e_1_3_1_15_2","doi-asserted-by":"crossref","first-page":"101949","DOI":"10.1016\/j.cose.2020.101949","article-title":"Protecting sensitive place visits in privacy-preserving trajectory publishing","volume":"97","author":"Wang Nana","year":"2020","unstructured":"Nana Wang and Mohan Kankanhalli. 2020. Protecting sensitive place visits in privacy-preserving trajectory publishing. Computers & Security 97 (2020), 101949.","journal-title":"Computers & Security"},{"key":"e_1_3_1_16_2","first-page":"5253","volume-title":"Proceedings of the 32nd USENIX Security Symposium (USENIX Security 23)","author":"Nicolas Carlini","year":"2023","unstructured":"Carlini Nicolas, Jamie Hayes, Milad Nasr, Matthew Jagielski, Vikash Sehwag, Florian Tramer, Borja Balle, Daphne Ippolito, and Eric Wallace. 2023. Extracting training data from diffusion models. In Proceedings of the 32nd USENIX Security Symposium (USENIX Security 23). USENIX Association, 5253\u20135270."},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382263"},{"key":"e_1_3_1_19_2","first-page":"213","volume-title":"Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Chen Rui","year":"2012","unstructured":"Rui Chen, Benjamin C. M. Fung, Bipin C. Desai, and N\u00e9riah M. Sossou. 2012. Differentially private transit data publication: A case study on the montreal transportation system. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 213\u2013221."},{"key":"e_1_3_1_20_2","first-page":"1154","volume-title":"Proceedings of the VLDB Endowment","author":"He Xi","year":"2015","unstructured":"Xi He, Graham Cormode, Ashwin Machanavajjhala, Cecilia M. Procopiuc, and Divesh Srivastava. 2015. DPT: Differentially private trajectory synthesis using hierarchical reference systems. In Proceedings of the VLDB Endowment. 1154\u20131165."},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3243734.3243741"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10207-020-00516-5"},{"issue":"8","key":"e_1_3_1_23_2","first-page":"1897","article-title":"LDPTrace: Locally differentially private trajectory synthesis","volume":"16","author":"Du Yuntao","year":"2023","unstructured":"Yuntao Du, Yujia Hu, Zhikun Zhang, Ziquan Fang, Lu Chen, Baihua Zheng, and Yunjun Gao. 2023. LDPTrace: Locally differentially private trajectory synthesis. PVLDB 16, 8 (2023), 1897\u20131909.","journal-title":"PVLDB"},{"issue":"10","key":"e_1_3_1_24_2","first-page":"2315","article-title":"Differentially private and utility preserving publication of trajectory data","volume":"18","author":"Emre Gursoy Mehmet","year":"2018","unstructured":"Mehmet Emre Gursoy, Ling Liu, Stacey Truex, and Lei Yu. 2018. Differentially private and utility preserving publication of trajectory data. IEEE Transactions on Mobile Computing 18, 10 (2018), 2315\u20132329.","journal-title":"IEEE Transactions on Mobile Computing"},{"key":"e_1_3_1_25_2","unstructured":"Retrieved from https:\/\/www.kaggle.com\/competitions\/pkdd-15-predict-taxi-service-trajectory-i\/data"},{"key":"e_1_3_1_26_2","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/2882903.2882928","volume-title":"Proceedings of the 2016 International Conference on Management of Data","author":"Zhang Jun","year":"2016","unstructured":"Jun Zhang, Xiaokui Xiao, and Xing Xie. 2016. Privtree: A differentially private algorithm for hierarchical decompositions. In Proceedings of the 2016 International Conference on Management of Data. ACM, 155\u2013170."},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cose.2017.02.002"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2018.07.007"},{"key":"e_1_3_1_29_2","doi-asserted-by":"crossref","first-page":"102634","DOI":"10.1016\/j.trc.2020.102634","article-title":"A differential privacy-based privacy-preserving data publishing algorithm for transit smart card data","volume":"115","author":"Li Yang","year":"2020","unstructured":"Yang Li, Dasen Yang, and Xianbiao Hu. 2020. A differential privacy-based privacy-preserving data publishing algorithm for transit smart card data. Transportation Research Part C: Emerging Technologies 115 (2020), 102634.","journal-title":"Transportation Research Part C: Emerging Technologies"},{"key":"e_1_3_1_30_2","first-page":"549","volume-title":"Proceedings of the 2015 IEEE Conference on Computer Communications (INFOCOM)","author":"Hua Jingyu","year":"2015","unstructured":"Jingyu Hua, Yue Gao, and Sheng Zhong. 2015. Differentially private publication of general time-serial trajectory data. In Proceedings of the 2015 IEEE Conference on Computer Communications (INFOCOM). IEEE, 549\u2013557."},{"key":"e_1_3_1_31_2","doi-asserted-by":"crossref","first-page":"113241","DOI":"10.1016\/j.eswa.2020.113241","article-title":"Novel trajectory privacy-preserving method based on clustering using differential privacy","volume":"149","author":"Zhao Xiaodong","year":"2020","unstructured":"Xiaodong Zhao, Dechang Pi, and Junfu Chen. 2020. Novel trajectory privacy-preserving method based on clustering using differential privacy. Expert Systems with Applications 149 (2020), 113241.","journal-title":"Expert Systems with Applications"},{"key":"e_1_3_1_32_2","doi-asserted-by":"crossref","first-page":"115120","DOI":"10.1016\/j.eswa.2021.115120","article-title":"Differentially private and utility-aware publication of trajectory data","volume":"180","author":"Liu Qi","year":"2021","unstructured":"Qi Liu, Juan Yu, Jianmin Han, and Xin Yao. 2021. Differentially private and utility-aware publication of trajectory data. Expert Systems with Applications 180 (2021), 115120.","journal-title":"Expert Systems with Applications"},{"issue":"7","key":"e_1_3_1_33_2","doi-asserted-by":"crossref","first-page":"1176","DOI":"10.1109\/JSTSP.2015.2425831","article-title":"The staircase mechanism in differential privacy","volume":"9","author":"Geng Quan","year":"2015","unstructured":"Quan Geng, Peter Kairouz, Sewoong Oh, and Pramod Viswanath. 2015. The staircase mechanism in differential privacy. IEEE Journal of Selected Topics in Signal Processing 9, 7 (2015), 1176\u20131184.","journal-title":"IEEE Journal of Selected Topics in Signal Processing"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2013.6691626"},{"key":"e_1_3_1_35_2","first-page":"170","volume-title":"Proceedings of the IFIP Annual Conference on Data and Applications Security and Privacy","author":"Roy Harichandan","year":"2016","unstructured":"Harichandan Roy, Murat Kantarcioglu, and Latanya Sweeney. 2016. Practical differentially private modeling of human movement data. In Proceedings of the IFIP Annual Conference on Data and Applications Security and Privacy. Springer, Cham, 170\u2013178."},{"key":"e_1_3_1_36_2","first-page":"1727","volume-title":"Proceedings of the 2022 IEEE 38th International Conference on Data Engineering","author":"Jin Fengmei","year":"2023","unstructured":"Fengmei Jin, Wen Hua, Boyu Ruan, and Xiaofang Zhou. 2023. Frequency-based randomization for guaranteeing differential privacy in spatial trajectories. In Proceedings of the 2022 IEEE 38th International Conference on Data Engineering. IEEE, 1727\u20131739."},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2022.12.027"},{"key":"e_1_3_1_38_2","doi-asserted-by":"crossref","first-page":"103066","DOI":"10.1016\/j.jnca.2021.103066","article-title":"DP-GAN: Differentially private consecutive data publishing using generative adversarial nets","volume":"185","author":"Ho Stella","year":"2021","unstructured":"Stella Ho, Youyang Qu, Bruce Gu, Longxiang Gao, Jianxin Li, and Yong Xiang. 2021. DP-GAN: Differentially private consecutive data publishing using generative adversarial nets. Journal of Network and Computer Applications 185 (2021), 103066.","journal-title":"Journal of Network and Computer Applications"},{"key":"e_1_3_1_39_2","article-title":"Generative adversarial nets","volume":"27","author":"Goodfellow Ian","year":"2014","unstructured":"Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, and Sherjil Ozair. 2014. Generative adversarial nets. Advances in Neural Information Processing Systems 27 (2014), 1--9.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1198\/1061860043524"},{"key":"e_1_3_1_41_2","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1145\/1559845.1559850","volume-title":"Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data","author":"McSherry Frank","year":"2009","unstructured":"Frank McSherry. 2009. Privacy integrated queries: An extensible platform for privacy-preserving data analysis. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. 19\u201330."},{"issue":"3","key":"e_1_3_1_42_2","first-page":"211","article-title":"The algorithmic foundations of differential privacy","volume":"9","author":"Dwork Cynthia","year":"2013","unstructured":"Cynthia Dwork and Aaron Roth. 2013. The algorithmic foundations of differential privacy. Theoretical Computer Science 9, 3-4 (2013), 211\u2013407.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"e_1_3_1_43_2","first-page":"32","article-title":"Geolife: A collaborative social networking service among user, location and trajectory","volume":"33","author":"Zheng Yu","year":"2010","unstructured":"Yu Zheng, Xing Xie, and Wei-Ying Ma. 2010. Geolife: A collaborative social networking service among user, location and trajectory. Bulletin of the Technical Committee on Data Engineering 33, 2 (2010), 32\u201339.","journal-title":"Bulletin of the Technical Committee on Data Engineering"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3778164","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T11:38:07Z","timestamp":1769081887000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3778164"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,22]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3,31]]}},"alternative-id":["10.1145\/3778164"],"URL":"https:\/\/doi.org\/10.1145\/3778164","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"value":"2374-0353","type":"print"},{"value":"2374-0361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,22]]},"assertion":[{"value":"2024-04-22","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-15","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-01-22","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}