PaTraS: A Path-Preserving Trajectory Simplification Method for Low-Loss Map Matching

Massive and redundant vehicle trajectory data is being accumulated and recorded at an unprecedented speed and scale, incurring expensive cost for storage, transmission, and query processing. Trajectory simplification is a typical way to reduce the size of raw trajectory as well as maintaining its structural information. However, existing methods mainly focus on preserving the shape of the trajectory while ignoring its influence on downstream applications. Since most applications require trajectories to be map-matched into paths before further processing, in this paper, we propose PaTraS, a path-preserving trajectory simplification method that aims to minimize the accuracy loss on the map-matching results of the compressed trajectories. To achieve this objective, we build an index that materializes the road network connectivity, and propose a connectivity-based similarity function that measures the importance of a trajectory point with respect to how it contributes to the map-matching results. Extensive experiments show that, compared with state-of-the-art methods, our proposed solution can better preserve the path generated by trajectory map-matching at the cost of a slightly increased running time, and it works effectively in both online and offline modes.