DOTS: An online and near-optimal trajectory simplification algorithm

The last decade witnessed an increasing number of location acquisition equipments such as mobile phone, smart watch etc. Trajectory data is collected with such a high speed that the location based services (LBS) meet challenge to process and take advantage of that big data. Good trajectory simplification (TS) algorithm thus plays an important role for both LBS providers and users as it significantly reduces processing and response time by minimizing the trajectory size with acceptable precision loss. State of the art TS algorithms work in batch mode and are not suitable for streaming data. The online solutions, on the other hand, usually use some heuristics which won't hold the optimality. This paper proposed a Directed acyclic graph based Online Trajectory Simplification (DOTS) method which solves the problem by optimization. Time complexity of DOTS is O(N2/M). A cascaded version of DOTS with time complexity of O(N) is also proposed. To our best knowledge, this is the first time that an optimal and online TS method is proposed. We find both the normal and cascaded DOTS outperform current TS methods like Douglas-Peucker (Douglas and Peucker, 1973), SQUISH (Muckell et al., 2011) etc. with pretty big margin.