A Graph-Based Min-# and Error-Optimal Trajectory Simplification Algorithm and Its Extension towards Online Services
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 algorithm...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2017-01-01
|
| Series: | ISPRS International Journal of Geo-Information |
| Subjects: | |
| Online Access: | http://www.mdpi.com/2220-9964/6/1/19 |
| _version_ | 1818560769744175104 |
|---|---|
| author | Fan Wu Kun Fu Yang Wang Zhibin Xiao |
| author_facet | Fan Wu Kun Fu Yang Wang Zhibin Xiao |
| author_sort | Fan Wu |
| collection | DOAJ |
| description | 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-ε 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. |
| first_indexed | 2024-12-14T00:42:31Z |
| format | Article |
| id | doaj.art-9584dca3435e41e7b1603c6a5d819de7 |
| institution | Directory Open Access Journal |
| issn | 2220-9964 |
| language | English |
| last_indexed | 2024-12-14T00:42:31Z |
| publishDate | 2017-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | ISPRS International Journal of Geo-Information |
| spelling | doaj.art-9584dca3435e41e7b1603c6a5d819de72022-12-21T23:24:18ZengMDPI AGISPRS International Journal of Geo-Information2220-99642017-01-01611910.3390/ijgi6010019ijgi6010019A Graph-Based Min-# and Error-Optimal Trajectory Simplification Algorithm and Its Extension towards Online ServicesFan Wu0Kun Fu1Yang Wang2Zhibin Xiao3Key Laboratory of Spatial Information Precessing and Application System Technology, Institude of Electronics, Chinese Academy of Sciences, Beijing 100190, ChinaKey Laboratory of Spatial Information Precessing and Application System Technology, Institude of Electronics, Chinese Academy of Sciences, Beijing 100190, ChinaKey Laboratory of Spatial Information Precessing and Application System Technology, Institude of Electronics, Chinese Academy of Sciences, Beijing 100190, ChinaKey Laboratory of Spatial Information Precessing and Application System Technology, Institude of Electronics, Chinese Academy of Sciences, Beijing 100190, ChinaTrajectory 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-ε 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.http://www.mdpi.com/2220-9964/6/1/19trajectory simplificationbreadth-first spanning treeshortest path searchdirected acyclic graph |
| spellingShingle | Fan Wu Kun Fu Yang Wang Zhibin Xiao A Graph-Based Min-# and Error-Optimal Trajectory Simplification Algorithm and Its Extension towards Online Services ISPRS International Journal of Geo-Information trajectory simplification breadth-first spanning tree shortest path search directed acyclic graph |
| title | A Graph-Based Min-# and Error-Optimal Trajectory Simplification Algorithm and Its Extension towards Online Services |
| title_full | A Graph-Based Min-# and Error-Optimal Trajectory Simplification Algorithm and Its Extension towards Online Services |
| title_fullStr | A Graph-Based Min-# and Error-Optimal Trajectory Simplification Algorithm and Its Extension towards Online Services |
| title_full_unstemmed | A Graph-Based Min-# and Error-Optimal Trajectory Simplification Algorithm and Its Extension towards Online Services |
| title_short | A Graph-Based Min-# and Error-Optimal Trajectory Simplification Algorithm and Its Extension towards Online Services |
| title_sort | graph based min and error optimal trajectory simplification algorithm and its extension towards online services |
| topic | trajectory simplification breadth-first spanning tree shortest path search directed acyclic graph |
| url | http://www.mdpi.com/2220-9964/6/1/19 |
| work_keys_str_mv | AT fanwu agraphbasedminanderroroptimaltrajectorysimplificationalgorithmanditsextensiontowardsonlineservices AT kunfu agraphbasedminanderroroptimaltrajectorysimplificationalgorithmanditsextensiontowardsonlineservices AT yangwang agraphbasedminanderroroptimaltrajectorysimplificationalgorithmanditsextensiontowardsonlineservices AT zhibinxiao agraphbasedminanderroroptimaltrajectorysimplificationalgorithmanditsextensiontowardsonlineservices AT fanwu graphbasedminanderroroptimaltrajectorysimplificationalgorithmanditsextensiontowardsonlineservices AT kunfu graphbasedminanderroroptimaltrajectorysimplificationalgorithmanditsextensiontowardsonlineservices AT yangwang graphbasedminanderroroptimaltrajectorysimplificationalgorithmanditsextensiontowardsonlineservices AT zhibinxiao graphbasedminanderroroptimaltrajectorysimplificationalgorithmanditsextensiontowardsonlineservices |