Extensive Comparison of Trajectory Simplification Algorithms

Abstract

In this study we compare ten simplification algorithms consisting of both line and trajectory simplification algorithms. Namely, Uniform Sampling, Douglas-Peucker, Visvalingam-Whyatt, Imai-Iri, TD-TR, SQUISH-E(μ), STTrace, OPW-TR, OPW-SP, and a newly introduced algorithm VW-TS. This newly introduced algorithm is an adaptation of the Visvalingam-Whyatt algorithm that uses Time-Space. This comparison is performed using three distinct real world datasets. Also, five error metrics are described and used to compare the simplifications’ performance. These five error metrics are: Spatial Distance, Temporal Distance, Speed Deviation, Heading Deviation, and Acceleration Deviation. TD-TR, VW-TS, and SQUISH-E(μ) prove to have the lowest error across all but one error metric. On the Acceleration Deviation metric, OPW-SP gives the lowest error with a significant margin.