Title: Encoding network-constrained travel trajectories using routing algorithms

Authors: Pablo Martinez Lerin; Daisuke Yamamoto; Naohisa Takahashi

Addresses: Graduate School of Engineering, Nagoya Institute of Technology, Gokiso, Showa, Nagoya, Aichi 466-8555, Japan ' Graduate School of Engineering, Nagoya Institute of Technology, Gokiso, Showa, Nagoya, Aichi 466-8555, Japan; Core Research for Evolutional Science and Technology, Japan Science and Technology Agency, K's Gobancho, 7, Gobancho, Chiyoda-ku, Tokyo 102-0076, Japan ' Graduate School of Engineering, Nagoya Institute of Technology, Gokiso, Showa, Nagoya, Aichi 466-8555, Japan

Abstract: This study proposes a generic encoder for network-constrained travel trajectories, and it implements two encoders by combining the proposed generic encoder with two routing algorithms, which reduce the size of a travel trajectory's path along a road network without modifying it. Although most previous trajectory compression methods introduce an error in the spatial component of trajectories to achieve compression, we argue that the path of a travel trajectory, i.e. the sequence of roads travelled, is crucial information for many applications. Experimental results obtained using a large-data set of real travel trajectories show that the two proposed encoders achieve high compression, outperforming a general purpose data compression method.

Keywords: network constrained trajectories; travel trajectories; trajectory encoding; lossless trajectory compression; shortest path; following path; routing algorithms; map matching; GPS; global positioning systems; GIS; geographical information systems; roads; road sequences.

DOI: 10.1504/IJKWI.2013.052724

International Journal of Knowledge and Web Intelligence, 2013 Vol.4 No.1, pp.34 - 49

Published online: 18 Mar 2013 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article