FedTraj: enabling effective federated trajectory clustering with hierarchical cross-silo interactions

Abstract

Trajectory clustering is a fundamental technique in mobility analysis, underpinning critical tasks such as route reconstruction, travel pattern discovery, and anomaly detection. With the widespread adoption of location-aware devices, trajectory data have become increasingly voluminous and geographically fragmented, residing across multiple organizations. Due to stringent privacy regulations, centralizing raw trajectory data for joint analysis is typically infeasible. Data federation offers a viable path toward collaborative trajectory analysis while respecting data privacy constraints. However, most existing trajectory clustering methods were developed under centralized assumptions and cannot be directly applied in federated settings. These methods face significant challenges when deployed across distributed data sources, including the lack of suitable distance metrics for heterogeneous trajectory data and the absence of efficient mechanisms for cluster generation under secure computation protocols. To address these challenges, we formally define the problem of federated trajectory clustering and propose FedTraj, a hierarchical framework tailored for clustering fine-grained trajectory data, i.e., trajectory segments. The framework consists of two core components: local clustering with cross-silo model training and sampling-based federated clustering. Additionally, we introduce a triangle inequality-based candidate enhancement mechanism to improve computational efficiency. Experimental results on real-world datasets demonstrate that FedTraj achieves promising performance in both clustering quality and running time. To the best of our knowledge, this work presents the first solution for secure and efficient trajectory segment clustering in federated settings.

Graphical abstract

Keywords

data federation / trajectory clustering / data privacy

References

[1] Si J, Yang J, Xiang Y, Li L, Tu B, Zhang R . ConDTC: contrastive deep trajectory clustering for fine-grained mobility pattern mining. IEEE Transactions on Big Data, 2025, 11( 2): 333–344

[2] Wang C, Lyu F, Wu S, Wang Y, Xu L, Zhang F, Wang S, Wang Y, Du Z . A deep trajectory clustering method based on sequence-to-sequence autoencoder model. Transactions in GIS, 2022, 26( 4): 1801–1820

[3] Hung C C, Peng W C, Lee W C . Clustering and aggregating clues of trajectories for mining trajectory patterns and routes. The VLDB Journal, 2015, 24( 2): 169–192

[4] Buchin K, Buchin M, Duran D, Fasy B T, Jacobs R, Sacristan V, Silveira R I, Staals F, Wenk C. Clustering trajectories for map construction. In: Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 2017, 14

[5] Han M, Xu K, Ma S, Li A, Jiang H . Federated learning-based trajectory prediction model with privacy preserving for intelligent vehicle. International Journal of Intelligent Systems, 2022, 37( 12): 10861–10879

[6] Wang C, Chen X, Wang J, Wang H. ATPFL: automatic trajectory prediction model design under federated learning framework. In: Proceedings of the 31st IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022, 6563–6572

[7] Chuah S P, Wu H, Lu Y, Yu L, Bressan S. Bus routes design and optimization via taxi data analytics. In: Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. 2016, 2417–2420

[8] Ma D, Fang B, Ma W, Wu X, Jin S . Potential routes extraction for urban customized bus based on vehicle trajectory clustering. IEEE Transactions on Intelligent Transportation Systems, 2023, 24( 11): 11878–11888

[9] Tong Y, She J, Ding B, Wang L, Chen L. Online mobile Micro-Task allocation in spatial crowdsourcing. In: Proceedings of the 32nd IEEE International Conference on Data Engineering. 2016, 49–60

[10] Goddard M . The EU General Data Protection Regulation (GDPR): European regulation that has a global impact. International Journal of Market Research, 2017, 59( 6): 703–705

[11] Chow C Y, Mokbel M F . Trajectory privacy in location-based services and data publication. ACM SIGKDD Explorations Newsletter, 2011, 13( 1): 19–29

[12] de Montjoye Y A, Hidalgo C A, Verleysen M, Blondel V D . Unique in the Crowd: the privacy bounds of human mobility. Scientific Reports, 2013, 3( 1): 1376

[13] Bater J, Elliott G, Eggen C, Goel S, Kho A, Rogers J . SMCQL: secure querying for federated databases. Proceedings of the VLDB Endowment, 2017, 10( 6): 673–684

[14] Volgushev N, Schwarzkopf M, Getchell B, Varia M, Lapets A, Bestavros A. Conclave: secure multi-party computation on big data. In: Proceedings of the 14th EuroSys Conference. 2019, 3

[15] Tong Y, Zeng Y, Song Y, Pan X, Fan Z, Xue C, Zhou Z, Zhang X, Chen L, Xu Y, Xu K, Lv W . Hu-Fu: efficient and secure spatial queries over data federation. The VLDB Journal, 2025, 34( 2): 19

[16] Wei S, Tong Y, Zhou Z, Xu Y, Gao J, Wei T, He T, Lv W . Federated reasoning LLMs: a survey. Frontiers of Computer Science, 2025, 19( 12): 1912613

[17] Yao D, Zhang C, Zhu Z, Huang J, Bi J. Trajectory clustering via deep representation learning. In: Proceedings of the 27th IEEE International Joint Conference on Neural Networks. 2017, 3880–3887

[18] Wu X, Zhang R, Li L. Clustering trajectories via sparse auto-encoders. In: Proceedings of the 4th IEEE International Conference on Multimedia Information Processing and Retrieval. 2021, 260–266

[19] Zhang R, Xie P, Jiang H, Xiao Z, Wang C, Liu L. Clustering noisy trajectories via robust deep attention auto-encoders. In: Proceedings of the 20th IEEE International Conference on Mobile Data Management. 2019, 63–71

[20] Tang W, Pi D, He Y. A density-based clustering algorithm with sampling for travel behavior analysis. In: Proceedings of the 17th International Conference on Intelligent Data Engineering and Automated Learning. 2016, 231–239

[21] Lee J G, Han J, Whang K Y. Trajectory clustering: a partition-and-group framework. In: Proceedings of the 33rd ACM SIGMOD International Conference on Management of Data. 2007, 593–604

[22] Fang Z, Du Y, Chen L, Hu Y, Gao Y, Chen G. E²DTC: an end to end deep trajectory clustering framework via self-training. In: Proceedings of the 37th IEEE International Conference on Data Engineering. 2021, 696–707

[23] Tong Y, Pan X, Zeng Y, Shi Y, Xue C, Zhou Z, Zhang X, Chen L, Xu Y, Xu K, Lv W . Hu-Fu: Efficient and secure spatial queries over data federation. Proceedings of the VLDB Endowment, 2022, 15( 6): 1159–1172

[24] Zheng Y . Trajectory data mining: an overview. ACM Transactions on Intelligent Systems and Technology, 2015, 6( 3): 29

[25] Douglas D H, Peucker T K . Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica: the International Journal for Geographic Information and Geovisualization, 1973, 10( 2): 112–122

[26] Keuper M, Andres B, Brox T. Motion trajectory segmentation via minimum cost multicuts. In: Proceedings of the 14th IEEE International Conference on Computer Vision. 2015, 3271–3279

[27] Liu M, He G, Long Y . A semantics-based trajectory segmentation simplification method. Journal of Geovisualization and Spatial Analysis, 2021, 5( 2): 19

[28] Chen Y, Zhang X, Wu C, Li G . Field-road trajectory segmentation for agricultural machinery based on direction distribution. Computers and Electronics in Agriculture, 2021, 186: 106180

[29] Murali A, Garg A, Krishnan S, Pokorny F T, Abbeel P, Darrell T, Goldberg K. TSC-DL: unsupervised trajectory segmentation of multi-modal surgical demonstrations with Deep Learning. In: Proceedings of the 33rd IEEE International Conference on Robotics and Automation. 2016, 4150–4157

[30] Yang Q, Liu Y, Chen T, Tong Y . Federated machine learning: concept and applications. ACM Transactions on Intelligent Systems and Technology, 2019, 10( 2): 12

[31] Ester M, Kriegel H P, Sander J, Xu X. A density-based algorithm for discovering clusters in large spatial databases with noise. In: Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. 1996, 226–231

[32] Li X, Zhao K, Cong G, Jensen C S, Wei W. Deep representation learning for trajectory similarity computation. In: Proceedings of the 34th IEEE International Conference on Data Engineering. 2018, 617–628

[33] Yang P, Wang H, Zhang Y, Qin L, Zhang W, Lin X. T3S: effective representation learning for trajectory similarity computation. In: Proceedings of the 37th International Conference on Data Engineering. 2021, 2183–2188

[34] Chang Y, Qi J, Liang Y, Tanin E. Contrastive trajectory similarity learning with dual-feature attention. In: Proceedings of the 39th IEEE International Conference on Data Engineering. 2023, 2933–2945

[35] Hochreiter S, Schmidhuber J . Long short-term memory. Neural Computation, 1997, 9( 8): 1735–1780

[36] Vaswani A, Shazeer N, Parmar N, Uszkoreit J, Jones L, Gomez A N, Kaiser Ł, Polosukhin I. Attention is all you need. In: Proceedings of the 31st International Conference on Neural Information Processing Systems. 2017, 6000–6010

[37] Li S, Ji Y, Shi D, Liao W, Zhang L, Tong Y, Xu K . A secure multi-party data federation system. International Journal of Software and Informatics, 2022, 12( 1): 107–129

[38] McMahan H B, Moore E, Ramage D, Hampson S, Arcas B A Y. Communication-efficient learning of deep networks from decentralized data. In: Proceedings of the 20th International Conference on Artificial Intelligence and Statistics. 2017, 1273–1282

[39] Tao Y, Both A, Silveira R I, Buchin K, Sijben S, Purves R S, Laube P, Peng D, Toohey K, Duckham M . A comparative analysis of trajectory similarity measures. GIScience & Remote Sensing, 2021, 58( 5): 643–669

[40] Yu Q, Luo Y, Chen C, Chen S . Trajectory similarity clustering based on multi-feature distance measurement. Applied Intelligence, 2019, 49( 6): 2315–2338

[41] Evans D, Kolesnikov V, Rosulek M . A pragmatic introduction to secure multi-party computation. Foundations and Trends in Privacy and Security, 2018, 2( 2-3): 70–246

[42] Wang Y, Zeng Y, Li S, Zhang Y, Zhou Z, Tong Y . Efficient and private federated trajectory matching. IEEE Transactions on Knowledge and Data Engineering, 2024, 36( 12): 8079–8092

[43] Porto taxi trajectory dataset. See www.kaggle.com/c/pkdd-15-predict-taxi-service-trajectory-i website, 2022

[44] Wang C, Chen L, Shang S, Jensen C S, Kalnis P. Multi-scale detection of anomalous spatio-temporal trajectories in evolving trajectory datasets. In: Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2024, 2980–2990

[45] Wang S, Bao Z, Culpepper J S, Sellis T, Qin X . Fast large-scale trajectory clustering. Proceedings of the VLDB Endowment, 2019, 13( 1): 29–42

[46] Vlachos M, Kollios G, Gunopulos D. Discovering similar multidimensional trajectories. In: Proceedings of the 18th International Conference on Data Engineering. 2002, 673–684

[47] Zhang Y Q, Shi G Y. Trajectory similarity measure design for ship trajectory clustering. In: Proceedings of the 6th IEEE International Conference on Big Data Analytics. 2021, 181–187

[48] Shahapure K R, Nicholas C. Cluster quality analysis using silhouette score. In: Proceedings of the 7th IEEE International Conference on Data Science and Advanced Analytics. 2020, 747–748

[49] Yang Y, Cai J, Yang H, Zhang J, Zhao X . TAD: a trajectory clustering algorithm based on spatial-temporal density analysis. Expert Systems with Applications, 2020, 139: 112846

[50] Wang W, Luan Z, He B, Li X, Zhang D, Huang Z, Tu W. A new hierarchical clustering approach for sparse mobile phone trajectories. In: Proceedings of the International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. 2018, 697–701

[51] Nanni M, Pedreschi D . Time-focused clustering of trajectories of moving objects. Journal of Intelligent Information Systems, 2006, 27( 3): 267–289

[52] Yue M, Li Y, Yang H, Ahuja R, Chiang Y Y, Shahabi C. DETECT: deep trajectory clustering for mobility-behavior analysis. In: Proceedings of the 7th IEEE International Conference on Big Data. 2019, 988–997

[53] Lochman Y, Olsson C, Zach C. Learned trajectory embedding for subspace clustering. In: Proceedings of the 33rd IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2024, 19092–19102

[54] MacQueen J B. Some methods for classification and analysis of multivariate observations. In: Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. 1967, 281–297

[55] Lu L, Lin Y, Wen Y, Zhu J, Xiong S . Federated clustering for recognizing driving styles from private trajectories. Engineering Applications of Artificial Intelligence, 2023, 118: 105714

[56] Paillier P. Public-key cryptosystems based on composite degree residuosity classes. In: Proceedings of the 17th Annual International Conference on the Theory and Applications of Cryptographic Techniques Advances in Cryptology. 1999, 223–238

[57] Özsu M T, Valduriez P. Principles of Distributed Database Systems. 4th ed. Cham: Springer, 2020

[58] Li N, Lyu M, Su D, Yang W. Differential Privacy: From Theory to Practice. Cham: Springer, 2017

[59] Bayatbabolghani F, Blanton M. Secure multi-party computation. In: Proceedings of the 25th ACM SIGSAC Conference on Computer and Communications Security. 2018, 2157–2159

[60] Bater J, He X, Ehrich W, Machanavajjhala A, Rogers J . Shrinkwrap: efficient SQL query processing in differentially private data federations. Proceedings of the VLDB Endowment, 2018, 12( 3): 307–320

[61] Bater J, Park Y, He X, Wang X, Rogers J . SAQE: practical privacy-preserving approximate query processing for data federations. Proceedings of the VLDB Endowment, 2020, 13( 12): 2691–2705

[62] Meng C, Rambhatla S, Liu Y. Cross-node federated graph neural network for spatio-temporal data modeling. In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2021, 1202–1211

[63] Liu Z, Miao H, Zhao Y, Liu C, Zheng K, Li H. LightTR: a lightweight framework for federated trajectory recovery. In: Proceedings of the 40th IEEE International Conference on Data Engineering. 2024, 4422–4434

RIGHTS & PERMISSIONS

Higher Education Press