M.Sc Thesis
M.Sc Student Gotsman Ranit Generating Map-based Routes from GPS Trajectories and their Compact Representation Department of Computer Science Dr. Yaron Kanza

Abstract

Digital maps are now an integral part of our lives, on computers, tablets and smartphone hardware platforms and they are integrated into many software applications, static and mobile, from location-based services to navigational aids. GPS receivers, capable of measuring location instantaneously and accurately, are also ubiquitous in most mobile platforms, enabling applications relating and combining GPS-measured locations and routes with digital maps.

This thesis deals with two practical problems related to GPS trajectories and digital maps. The first is the classical problem of map matching, namely matching a given (possibly noisy or sparse) GPS trajectory to the sequence of roads traversed by the GPS receiver in reality. We provide a novel solution to this problem, a modification of an existing method based on Hidden Markov Models (HMM). Our algorithm works well also in scenarios where the GPS measurements are very sparse and noisy, which is lacking in the existing HMM approaches.

The second problem we deal with is the compact coding of routes on digital maps. A route is a sequence of vertices in the embedded planar graph representing a map, typically describing a route taken by a mobile vehicle. An emerging problem is how to efficiently code these data sets in a world where millions of these routes are generated each day, and all have to be stored and/or transmitted for future processing in large databases. We provide two methods to code digital routes. The first method represents the given route as a sequence of so-called greedy paths, where a greedy path between vertex s and vertex t is one where the Euclidean distance to t is minimized as each edge of the path is traversed. We provide two algorithms to generate a greedy-path code for a route containing n vertices. The first algorithm is fast - it has O(n) time complexity, and the second one is slower - having O(n2) 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 codes a route as a sequence of (classical) shortest paths. We provide a simple algorithm to generate a shortest-path code in O(kn2 log n) time, where k is the length of the (output) code, and prove that this code is optimal. Decoding a shortest-path code also requires O(kn2 log n) time. Experimentally, we observed that shortest-path codes are much more compact than greedy-path codes, justifying the larger time complexity.