A Heading Maintaining Oriented Compression Algorithm for GPS Trajectory Data

Hao, Pengfei; Yao, Chunlong; Meng, Qingbin; Yu, Xiaoqiang; Li, Xu

doi:10.15388/Informatica.2019.196

Informatica

A Heading Maintaining Oriented Compression Algorithm for GPS Trajectory Data

Volume 30, Issue 1 (2019), pp. 33–52

Pengfei Hao Chunlong Yao Qingbin Meng Xiaoqiang Yu Xu Li

https://doi.org/10.15388/Informatica.2019.196

Pub. online: 1 January 2019 Type: Research Article

Open Access

Received
1 October 2017

Accepted
1 November 2018

Published
1 January 2019

Abstract

The raw trajectories contain large amounts of redundant data that bring challenges to storage, transmission and processing. Trajectory compression algorithms can reduce the number of positioning points while minimizing the loss of information. This paper proposes a heading maintaining oriented trajectory compression algorithm, which takes into account both position information and direction information. By setting an angle threshold, the algorithm can achieve a more accurate approximation of trajectories than traditional position-preserving trajectory compression algorithms. The experimental results show that the algorithm can ensure certain effect on the direction information and is more flexible.

References

Cao, W., Li, Y. (2017). Dots: an online and near-optimal trajectory simplification algorithm. Journal of Systems Software, 126, 34–44.

Chen, Y., Jiang, K., Zheng, Y., Li, C., Yu, N. (2009). Trajectory simplification method for location-based social networking services. In: Proceedings of the 2009 International Workshop on Location Based Social Networks, Seattle, USA, pp. 33–40.

Chen, M., Xu, M., Franti, P. (2012). A fast $O(N)$ multiresolution polygonal approximation algorithm for GPS trajectory simplification. IEEE Transactions on Image Processing, 21(5), 2770–2785.

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

Giannotti, F., Nanni, M., Pinelli, F., Pedreschi, D. (2007). Trajectory pattern mining. In: Proceedings of the 13th ACM SIGKDD international conference on Knowledge Discovery and Data Mining, San Jose, USA, pp. 330–339.

Jiagao, W.U., Qian, K., Liu, M., Liu, L. (2015). Improvement of perez and vidal algorithm for the decomposition of digitized curves into line segments. Journal of Computer Applications, 35(5), 1209–1212.

Kolesnikov, A., Franti, P. (2002). A fast near-optimal min-# polygonal approximation of digitized curves. In: IASTED Internatioal. Conference on Automation, Control and Information Technology (ACIT 2002), Novosibirsk, Russia, pp. 418–422.

Kolesnikov, A., Franti, P. (2003). Reduced-search dynamic programming for approximation of polygonal curves. Pattern Recognition Letters, 24(14), 2243–2254.

Li, T., Pei, T., Yuan, Y., Song, C., Wang, W., Yang, G. (2014). A review on the classification, patterns and applied research of human mobility trajectory. Progress in Geography, 33(7), 938–948.

Long, C., Wong, C.-W. Jagadish H. V, R. (2013). Direction-preserving trajectory simplification. Proceedings of the VLDB Endowment, 6(10), 949–960.

Meratnia, N., de By, R. (2004). Spatiotemporal compression techniques for moving point objects. In: Advances in Database Technology – EDBT 2004, 9th International Conference on Extending Database Technology, Heraklion, Crete, Greece, pp. 765–782.

Morzy, M., Rosikiewicz, L. (2007). Mining frequent trajectories of moving objects for location prediction. In: Machine Learning and Data Mining in Pattern Recognition, 5th International Conference, MLDM 2007, Leipzig, Germany, pp. 667–680.

Muckell, J., Hwang, J.-H., Patil, V., Lawson, C.T., Ping, F., Ravi, S.S. (2011). SQUISH: an online approach for GPS trajectory compression. In: Proceedings of the 2nd International Conference and Exhibition on Computing for Geospatial Research & Application, COM.Geo 2011, Washington, DC, USA, May, pp. 23–25.

Muckell, J., Olsen, P.W., Hwang, J.H., Lawson, C.T., Ravi, S.S. (2014). Compression of trajectory data: a comprehensive evaluation and new approach. GeoInformatica, 18(3), 435–460.

Perez, J.C., Vidal, E. (1994). Optimum polygonal approximation of digitized curves. Pattem Recognition Letters, 15(8), 743–750.

Potamias, M., Patroumpas, K., Sellis, T. (2006). Sampling trajectory streams with spatiotemporal criteria. In: Proceedings of the 18th International Conference on Scientific and Statistical Database Management (SSDBM ’06), Vienna, Austria, 3–5 July 2006, pp. 275–284.

Qian, H., Lu, Y. (2017). Simplifying gps trajectory data with enhanced spatial-temporal constraints. International Journal of Geo-Information, 6(11), 329.

Salotti, M. (2000). Improvement of Perez and Vidal algorithm for the decomposition of digitized curves into line segments. In: Proceedings International Conference on Pattern Recognition ICPR’00, Barcelona, Spain, pp. 882–886.

Salotti, M. (2001). An efficient algorithm for the optimal polygonal approximation of digitized curves. Pattern Recognition Letters, 22(2), 215–221.

Sun, P., Xia, S., Yuan, G., Li, D. (2016). An overview of moving object trajectory compression algorithms. Mathematical Problems in Engineering, 2016(3), 1–13.

Tian, S.L., Xu, J. (2011). GPS location data reducing based on turning point judgment method. In: Second International Conference on Mechanic Automation and Control Engineering (MACE), Hohhot, China, pp. 7395–7398.

Yuan, J. (2012). Querying, Mining with Applications on Large-Scale Trajectory Data. HeFei University of Science and Technology of China.

Zheng, Y., Da-Ke, H.E., Zhang, W.F. et al. (2005). An efficient scheme for GPS data compression. China Railway Science, 26(3), 134–138.

Zheng, Y., Li, Q., Chen, Y., Xie, X., Ma, W.-Y. (2008). Understanding mobility based on GPS data. In: Proceedings of the 10th ACM Conference on Ubiquitous Computing (Ubicomp 2008), Seoul, Korea, pp. 312–321.

Zheng, Y., Zhang, L., Xie, X., Ma, W.-Y. (2009). Mining interesting locations and travel sequences from GPS trajectories. In: Proceedings of International Conference on World Wild Web (WWW 2009). ACM Press, Madrid, Spain, pp. 791–800.

Zheng, Y., Xie, X., Ma, W.-Y. (2010). GeoLife: a collaborative social networking service among user, location and trajectory. Bulletin of the Technical Committee on Data Engineering, 33(2), 32–40.

Biographies

Hao Pengfei

P. Hao, born in 1991, MS candidate. His research interests include data mining.

Yao Chunlong

yaocl@dlpu.edu.cn

C. Yao, born in 1971, PhD, professor. His research interests include database theory and application, data mining, intelligent transportation.

Meng Qingbin

Q. Meng, born in 1991, MS, professor. His research interests include data mining.

Yu Xiaoqiang

X. Yu, born in 1974, PhD, associate professor. His research interests include computer application.

Li Xu

X. Li, born in 1981, PhD, associate professor. Her research interests include machine learning.

Full article Cited by

Open access article under the CC BY license.

Keywords

trajectory compression heading maintaining flexible

Metrics (since January 2020)

45 Article info views	24 Full article views
681 PDF downloads	198 XML downloads

RSS

Authors

Abstract

References

Biographies

Export citation

Copy and paste formatted citation

Download citation in file