M.Sc Thesis | |

M.Sc Student | Gotsman Ranit |
---|---|

Subject | Generating Map-based Routes from GPS Trajectories and their Compact Representation |

Department | Department of Computer Science |

Supervisor | DR. Yaron Kanza |

Full Thesis text |

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*(*n*^{2}) 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*(*kn*^{2}
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*(*kn*^{2
}log *n*) time. Experimentally, we observed that shortest-path codes
are much more compact than greedy-path codes, justifying the larger time
complexity.