Efficient path decoding from high sampling trace data using TSPS

With reduced storage costs and increased network bandwidth, map matching (MM) or path decoding from high sampling trace data for all private and shared vehicles, bicycles, etc., is anticipated in the near future. To save the storage space, traditional MM methods are often designed in a step-by-step manner for low sampling trace with a time interval above 1 min. But the step-wise matching logic is naturally inefficient for high sampling trace. We propose integrating all path developing work into only one trace-oriented shortest path search (TSPS). Five existing MM algorithms with different speedup strategies are used to benchmark the performance of TSPS. The experiment results conducted on two trajectory datasets validated that the proposed algorithm has an outstanding working efficiency by up to four orders of magnitude without loss of accuracy.