{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:29:33Z","timestamp":1760441373407,"version":"build-2065373602"},"reference-count":26,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2017,1,16]],"date-time":"2017-01-16T00:00:00Z","timestamp":1484524800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Trajectory simplification has become a research hotspot since it plays a significant role in the data preprocessing, storage, and visualization of many offline and online applications, such as online maps, mobile health applications, and location-based services. Traditional heuristic-based algorithms utilize greedy strategy to reduce time cost, leading to high approximation error. An Optimal Trajectory Simplification Algorithm based on Graph Model (OPTTS) is proposed to obtain the optimal solution in this paper. Both min-# and min-\u03b5 problems are solved by the construction and regeneration of the breadth-first spanning tree and the shortest path search based on the directed acyclic graph (DAG). Although the proposed OPTTS algorithm can get optimal simplification results, it is difficult to apply in real-time services due to its high time cost. Thus, a new Online Trajectory Simplification Algorithm based on Directed Acyclic Graph (OLTS) is proposed to deal with trajectory stream. The algorithm dynamically constructs the breadth-first spanning tree, followed by real-time minimizing approximation error and real-time output. Experimental results show that OPTTS reduces the global approximation error by 82% compared to classical heuristic methods, while OLTS reduces the error by 77% and is 32% faster than the traditional online algorithm. Both OPTTS and OLTS have leading superiority and stable performance on different datasets.<\/jats:p>","DOI":"10.3390\/ijgi6010019","type":"journal-article","created":{"date-parts":[[2017,1,16]],"date-time":"2017-01-16T09:44:02Z","timestamp":1484559842000},"page":"19","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A Graph-Based Min-# and Error-Optimal Trajectory Simplification Algorithm and Its Extension towards Online Services"],"prefix":"10.3390","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3216-6534","authenticated-orcid":false,"given":"Fan","family":"Wu","sequence":"first","affiliation":[{"name":"Key Laboratory of Spatial Information Precessing and Application System Technology, Institude of Electronics, Chinese Academy of Sciences, Beijing 100190, China"},{"name":"University of Chinese Academy of Sciences, Beijing 100190, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kun","family":"Fu","sequence":"additional","affiliation":[{"name":"Key Laboratory of Spatial Information Precessing and Application System Technology, Institude of Electronics, Chinese Academy of Sciences, Beijing 100190, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yang","family":"Wang","sequence":"additional","affiliation":[{"name":"Key Laboratory of Spatial Information Precessing and Application System Technology, Institude of Electronics, Chinese Academy of Sciences, Beijing 100190, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1781-580X","authenticated-orcid":false,"given":"Zhibin","family":"Xiao","sequence":"additional","affiliation":[{"name":"Key Laboratory of Spatial Information Precessing and Application System Technology, Institude of Electronics, Chinese Academy of Sciences, Beijing 100190, China"},{"name":"University of Chinese Academy of Sciences, Beijing 100190, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2017,1,16]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Zheng, Y., and Zhou, X. (2011). Computing with Spatial Trajectories, Springer.","DOI":"10.1007\/978-1-4614-1629-6"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Meratnia, N., and de By, R.A. (2004, January 14\u201318). Spatiotemporal compression techniques for moving point objects. Proceedings of the 9th International Conference on Extending Database Technology, Heraklion, Greece.","DOI":"10.1007\/978-3-540-24741-8_44"},{"key":"ref_3","unstructured":"Melkman, A., and O\u2019Rourke, J. (1988). Computational Morphology, Elsevier Science."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1016\/S0031-3203(01)00051-6","article-title":"Optimal polygonal approximation of digitized curves using the sum of square deviations criterion","volume":"35","author":"Salotti","year":"2002","journal-title":"Pattern Recognit."},{"key":"ref_5","unstructured":"Imai, H., and Iri, M. (1988). Computational Morphology, Elsevier Science."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"2770","DOI":"10.1109\/TIP.2012.2186146","article-title":"A fast multiresolution polygonal approximation algorithm for GPS trajectory simplification","volume":"21","author":"Chen","year":"2012","journal-title":"IEEE Trans. Image Process."},{"key":"ref_7","first-page":"112","article-title":"Algorithms for the reduction of the number of points required to represent a digitized line or its caricature","volume":"10","author":"Douglas","year":"1973","journal-title":"Cartogr. Int. J. Geogr. Inf. Geovis."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1016\/0167-8655(95)80001-A","article-title":"An algorithm for polygonal approximation based on iterative point elimination","volume":"16","author":"Pikaz","year":"1995","journal-title":"Pattern Recognit. Lett."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/PL00009500","article-title":"Efficient algorithms for approximating polygonal chains","volume":"23","author":"Agarwal","year":"2000","journal-title":"Discret. Comput. Geom."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.comgeo.2004.07.001","article-title":"Polygonal chain approximation: A query based approach","volume":"30","author":"Daescu","year":"2005","journal-title":"Comput. Geom. Theory Appl."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"2243","DOI":"10.1016\/S0167-8655(03)00051-5","article-title":"Reduced-search dynamic programming for approximation of polygonal curves","volume":"24","author":"Kolesnikov","year":"2003","journal-title":"Pattern Recognit. Lett."},{"key":"ref_12","unstructured":"Potamias, M., Patroumpas, K., and Sellis, T. (2006, January 3\u20135). In sampling trajectory streams with spatiotemporal criteria. Proceedings of the 18th International Conference on Scientific and Statistical Database Management, Vienna, Austria."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1145\/3147.3165","article-title":"Random sampling with a reservoir","volume":"11","author":"Vitter","year":"1985","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_14","unstructured":"Keogh, E., Chu, S., and Pazzani, M. (December, January 29). An online algorithm for segmenting time series. Proceedings of the 2001 IEEE International Conference on Data Mining, San Jose, CA, USA."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1007\/s10707-013-0184-0","article-title":"Compression of trajectory data: A comprehensive evaluation and new approach","volume":"18","author":"Muckell","year":"2014","journal-title":"Geoinformatica"},{"key":"ref_16","first-page":"461","article-title":"Combinatorial optimization: Networks and matroids","volume":"84","author":"Lawler","year":"2001","journal-title":"Bull. Am. Math. Soc."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1142\/S0218195903001104","article-title":"Space-efficient algorithms for approximation polygonal curves in two-dimentional space","volume":"13","author":"Chen","year":"2003","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"ref_19","unstructured":"Kolesnikov, A., and Fr\u00e4nti, P. (2002, January 10\u201313). A fast near-optimal min-# polygonal approximation of digitized curves. Proceedings of the IASTED International Conference on Automation, Control and Information Technology-ACIT\u201902, Novosibirsk, Russia."},{"key":"ref_20","unstructured":"Mopsi Project. Available online: http:\/\/cs.joensuu.fi\/mopsi\/."},{"key":"ref_21","first-page":"32","article-title":"Geolife: A collaborative social networking service among user, location and trajectory","volume":"33","author":"Zheng","year":"2010","journal-title":"IEEE Data Eng. Bull."},{"key":"ref_22","unstructured":"Movebank. Available online: http:\/\/www.movebank.org."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Xiang, L., Gao, M., and Wu, T. (2016). Extracting stops from noisy trajectories: A sequence oriented clustering approach. ISPRS Int. J. Geo-Inf., 5.","DOI":"10.3390\/ijgi5030029"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Fu, Z., Tian, Z., Xu, Y., and Qiao, C. (2016). A two-step clustering approach to extract locations from individual GPS trajectory data. ISPRS Int. J. Geo-Inf., 5.","DOI":"10.3390\/ijgi5100166"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Kolesnikov, A., Franti, P., and Wu, X. (2004, January 23\u201326). Multiresolution polygonal approximation of digital curves. Proceedings of the 17th International Conference on Pattern Recognition, ICPR 2004, Cambridge, UK.","DOI":"10.1109\/ICPR.2004.1334393"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/s10044-008-0133-y","article-title":"Speeding up simplification of polygonal curves using nested approximations","volume":"12","author":"Marteau","year":"2009","journal-title":"Pattern Anal. Appl."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/6\/1\/19\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:26:18Z","timestamp":1760207178000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/6\/1\/19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,16]]},"references-count":26,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2017,1]]}},"alternative-id":["ijgi6010019"],"URL":"https:\/\/doi.org\/10.3390\/ijgi6010019","relation":{},"ISSN":["2220-9964"],"issn-type":[{"type":"electronic","value":"2220-9964"}],"subject":[],"published":{"date-parts":[[2017,1,16]]}}}