The Taub Faculty of Computer Science Events and Talks

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.