Master Thesis MSTR-2016-38

BibliographyTangermann, Jonas: Incremental Weak Fréchet Map-Matching.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Master Thesis No. 38 (2016).
69 pages, english.
CR-SchemaE.1 (Data Structures)
F.2.2 (Nonnumerical Algorithms and Problems)
G.2.2 (Discrete Mathematics Graph Theory)
Abstract

Many geographic information systems share the common task of mapping positional data given as trajectories onto a given map, the so-called map-matching. One category of approaches to solve this problem are geometric map-matching algorithms utilizing the Fréchet metric. To find the optimal match, these approaches either use parametric search and depth-first search or a modified version of Dijkstra’s algorithm. In this thesis a weak Fréchet based map-matching algorithm for undirected graphs is developed, which avoids the above-mentioned techniques with the objective of computation speed improvements. Furthermore, this algorithm is designed to support parallelization through its incremental nature. The proposed approach is evaluated by comparing theoretical complexities as well as experimental evaluation against the Dijkstra basted approach of Wenk et al.[WSP06]. The evaluation, however, only yielded indications for positive results under heavy use of parallelization.

Full text and
other links
PDF (2490125 Bytes)
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Algorithmic
Superviser(s)Funke, Prof. Stafen; Seybold, Martin
Entry dateAugust 1, 2018
   Publ. Computer Science