Network Trajectory Protection

Lulu Wang

¹Shenzhen University, Shenzhen, China

²University of Macau, Macau, China

³Beijing Normal University, Beijing, China

⁴The Chinese University of Hong Kong, Hong Kong, China

*Corresponding author

In modern computer networks, the transmission of messages forms a sequence through multiple intermediate nodes, which can be represented as network trajectories. These trajectories provide essential information for routing optimization and security auditing. However, the former requires learning the clear trajectory, while the latter needs to hide the details of the trajectory. There is a contradiction between the need for accurate trajectory analysis and the need to conceal sensitive details. To balance these objectives, trajectory simplification becomes essential: reducing the number of recorded nodes while preserving the overall structure. Yet, existing simplification algorithms primarily target trajectories with nodes described by 2-dimensional vectors and are inadequate for multi-dimensional settings. To address this, we propose the Network Trajectory Protection (NTP) problem: given a multi-dimensional trajectory and a simplification budget, the goal is to select a subset of nodes that best approximates the original trajectory under a Euclidean distance-based loss metric. We prove that the NTP problem is NP-hard and design an efficient greedy approximation algorithm. We conduct extensive experiments on network trajectory datasets, demonstrating the superior effectiveness and efficiency of our algorithms compared to baselines.

Network Trajectory, Protection, Trajectory Simplification

Qianting Chen, Lulu Wang, Ke Chao, Weicheng Wang, Rui Mao (2025). Network Trajectory Protection. Journal of Networking and Network Applications, Volume 5, Issue 1, pp. 39–47. https://doi.org/10.33969/J-NaNA.2025.050104.

[1] S. Chakrabarty and D. W. Engels, “Secure smart cities framework using iot and ai,” in 2020 IEEE Global Conference on Artificial Intelligence and Internet of Things (GCAIoT), 2020.

[2] X. Zhao, J. Qiao, X. Huang, C. Wang, S. Song, and J. Wang, “Apache tsfile: An iot-native time series file format,” Proceedings of the VLDB Endowment, vol. 17, no. 12, pp. 4064–4076, 2024.

[3] T. Chang and O. Khan, “Rapdad: A low latency desynchronization approach for 6tisch-based asset tracking networks,” IEEE Transactions on Industrial Informatics, pp. 1–13, 2025.

[4] A. Rejeb, K. Rejeb, H. Treiblmaier, A. Appolloni, S. Alghamdi, Y. Alhasawi, and M. Iranmanesh, “The internet of things (iot) in healthcare: Taking stock and moving forward,” Internet of Things, vol. 22, p. 100721, 2023.

[5] F. Al-Turjman, M. H. Nawaz, and U. D. Ulusar, “Intelligence in the internet of medical things era: A systematic review of current and future trends,” Computer Communications, vol. 150, pp. 644–660, 2020.

[6] N. Meratnia and A. Rolf, “Spatiotemporal compression techniques for moving point objects,” in International Conference on Extending Database Technology. Springer, 2004, pp. 765–782.

[7] M. Potamias, K. Patroumpas, and T. Sellis, “Sampling trajectory streams with spatiotemporal criteria,” in 18th International Conference on Scientific and Statistical Database Management, 2006.

[8] H. Li, L. Kulik, and K. Ramamohanarao, “Spatio-temporal trajectory simplification for inferring travel paths,” in SIGSPATIAL, 2014, pp. 63–72.

[9] J. Muckell, J.-H. Hwang, V. Patil, C. T. Lawson, F. Ping, and S. Ravi, “Squish: an online approach for gps trajectory compression,” in Proceedings of the 2nd international conference on computing for geospatial research & applications, 2011, pp. 1–8.

[10] J. Muckell, P. W. Olsen, J.-H. Hwang, C. T. Lawson, and S. Ravi, “Compression of trajectory data: a comprehensive evaluation and new approach,” GeoInformatica, vol. 18, no. 3, pp. 435–460, 2014.

[11] V. Chvatal, “A greedy heuristic for the set-covering problem,” Math. Oper. Res., vol. 4, no. 3, p. 233–235, Aug. 1979.

[12] M. R. Garey and D. S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness. USA: W. H. Freeman & Co., 1990.

[13] K. G. Jamieson and R. D. Nowak, “Active ranking using pairwise comparisons,” in NIPS, 2011.

[14] W. Wang, R. C.-W. Wong, and M. Xie, “Interactive search for one of the top-k,” in SIGMOD. New York, NY, USA: ACM, 2021.

[15] R. C.-W. W. Weicheng Wang and M. Xie, “Interactive search with mixed attributes,” in ICDE, 2023.

[16] J. Muckell, P. W. Olsen, J.-H. Hwang, C. T. Lawson, and S. Ravi, “Compression of trajectory data: a comprehensive evaluation and new approach,” GeoInformatica, vol. 18, no. 3, pp. 435–460, 2014.

[17] R. Bellman, “On the approximation of curves by line segments using dynamic programming,” Communications of the ACM, vol. 4, no. 6, p. 284, 1961.

[18] E. Keogh, S. Chu, D. Hart, and M. Pazzani, “An online algorithm for segmenting time series,” in Proceedings 2001 IEEE international conference on data mining. IEEE, 2001, pp. 289–296.

[19] C. Long, R. C.-W. Wong, and H. Jagadish, “Trajectory simplification: On minimizing the direction-based error,” VLDB, vol. 8, no. 1, pp. 49–60, 2014.

[20] D. Zhang, M. Ding, D. Yang, Y. Liu, J. Fan, and H. T. Shen, “Trajectory simplification: an experimental study and quality analysis,” VLDB, 2018.

[21] X. Lin, J. Jiang, S. Ma, Y. Zuo, and C. Hu, “One-pass trajectory simplification using the synchronous euclidean distance,” The VLDB Journal, vol. 28, no. 6, pp. 897–921, 2019.

[22] J. Liu, K. Zhao, P. Sommer, S. Shang, B. Kusy, and R. Jurdak, “Bounded quadrant system: Error-bounded trajectory compression on the go,” in ICDE, 2015, pp. 987–998.

[23] J. Liu, K. Zhao, P. Sommer, S. Shang, B. Kusy, J.-G. Lee, and R. Jurdak, “A novel framework for online amnesic trajectory compression in resource-constrained environments,” TKDE, vol. 28, no. 11, pp. 2827–2841, 2016.

[24] X. L. S. Ma and H. Z. T. W. J. Huai, “One-pass error bounded trajectory simplification,” VLDB, vol. 10, no. 7, 2017.

[25] C. Long, R. C.-W. Wong, and H. Jagadish, “Direction-preserving trajectory simplification,” VLDB, vol. 6, no. 10, pp. 949–960, 2013.

[26] B. Ke, J. Shao, Y. Zhang, D. Zhang, and Y. Yang, “An online approach for direction-based trajectory compression with error bound guarantee,” in Asia-Pacific Web Conference. Springer, 2016.

[27] W. Cao and Y. Li, “Dots: An online and near-optimal trajectory simplification algorithm,” Journal of Systems and Software, 2017.

[28] Z. Wang, C. Long, and G. Cong, “Trajectory simplification with reinforcement learning,” in 2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE, 2021, pp. 684–695.

[29] Z. Wang, C. Long, G. Cong, and Q. Zhang, “Error-bounded online trajectory simplification with multi-agent reinforcement learning,” in Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2021, pp. 1758–1768.

[30] Z. Wang, C. Long, G. Cong, and C. S. Jensen, “Collectively simplifying trajectories in a database: A query accuracy driven approach,” in ICDE, 2024, pp. 4383–4395.

[31] Z. Fang, C. He, L. Chen, D. Hu, Q. Sun, L. Li, and Y. Gao, “A lightweight framework for fast trajectory simplification,” in ICDE, 2023, pp. 2386–2399.