Beta 1


Title Practical Polyline Matching for GPS Data
Author Gjaldbæk, Martin
Supervisor Bille, Philip (Algorithms and Logic, Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
Institution Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
Thesis level Master's thesis
Year 2010
Abstract Partial route matching is the problem of comparing two routes — polylines consisting of sequential geographical coordinates — and matching them based on their proximity to each other. Even if a perfect matching is not found then the parts of the routes that do match must be identified as such. The proposed algorithm rasterizes the routes into two sequences of grid fields. These can then be treated like strings of characters and are matched using an approximate string matching algorithm. Its cost function is modified so it is based on the length of the routes rather than edit distance. Unlike characters, grid fields match if they are close to each other in the grid. Furthermore the basic algorithm is modified to allow a single “character” to match multiple others. The complexity is O(mn), m and n being the number of grid fields in the rasterized routes. While these are dependent on the rasterization, it is shown that if the lateral grid size is bounded by the average line segment length, then the complexity is bounded by O(st), where s and t are the number of line segments in the routes. The algorithm is tested on a dataset made by GPS-tracking runners and cyclists and is found to be both feasible and capable of consistently producing the desired results.
Imprint Technical University of Denmark (DTU) : Kgs. Lyngby, Denmark
Series IMM-M.Sc.-2010-81
Fulltext
Original PDF ep10_81.pdf (1.85 MB)
Admin Creation date: 2010-10-26    Update date: 2010-10-26    Source: dtu    ID: 268267    Original MXD