A Dilution-matching-encoding compaction of trajectories over road networks

Many devices nowadays record traveled routes as sequences of GPS locations. With the growing popularity of smartphones, millions of such routes are generated each day, and many routes have to be stored locally on the device or transmitted to a remote database. It is, thus, essential to encode the sequences, in order to decrease the volume of the stored or transmitted data. In this paper we study the problem of encoding routes over a vectorial road network (map), where GPS locations can be associated with vertices or with road segments. We consider a three-step process of dilution, map-matching and coding, which helps reducing the amount of transmitted data between the cellular device and remote servers. We present two methods to code routes. The first method represents the given route as a sequence of greedy paths. We provide two algorithms to generate a greedy-path code for a sequence of n vertices on the map. The first algorithm has O(n) time complexity, and the second one has O(n ²) time complexity, but it is optimal, meaning that it generates the shortest possible greedy-path code. Decoding a greedy-path code can be done in O(n) time. The second method encodes a route as a sequence of shortest paths. We provide algorithms to generate unidirectional and bidirectional optimal shortest-path codes. Encoding and decoding a shortest-path code can be done in O(k n ² logn) time, where k is the length of the produced code, assuming the graph valency is bounded. Our experimental evaluation shows that shortest-path codes are more compact than greedy-path codes, justifying the larger time complexity.