Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Generating Map-based Routes from GPS Trajectories and their Compact Representation
event speaker icon
Ranit Gotsman (M.Sc. Thesis Seminar)
event date icon
Wednesday, 19.12.2012, 13:00
event location icon
Taub 601
event speaker icon
Advisor: Prof. Y. Kanza
Digital maps and devices with an integrated GPS receiver, such as smartphones, are now an integral part of our lives. We deal with two practical problems related to GPS trajectories and digital maps. The first problem is the classical problem of map-matching; namely, matching a given GPS trajectory, possibly noisy or sparse, to the sequence of actual roads traversed by the carrier of the GPS receiver. We provide a novel solution to this problem. Our algorithm is adapted to work well in scenarios where the GPS measurements are very sparse and noisy, and in such scenarios, it outperforms other map-matching algorithms that are based on Hidden Markov Models. The second problem we deal with is the compact coding of routes on digital maps. Efficiently coding routes is essential in a world where the millions of routes generated each day need to be stored efficiently. We provide two methods of coding digital routes. The first method represents the given route as a sequence of greedy paths. The second method codes a route as a sequence of shortest paths. Our experimental evaluation shows that the shortest path codes are much more compact than the greedy path codes, justifying the higher time complexity.