Masterarbeit MSTR-2016-38

Bibliograph.
Daten
Tangermann, Jonas: Incremental Weak Fréchet Map-Matching.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Masterarbeit Nr. 38 (2016).
69 Seiten, englisch.
CR-Klassif.E.1 (Data Structures)
F.2.2 (Nonnumerical Algorithms and Problems)
G.2.2 (Discrete Mathematics Graph Theory)
Kurzfassung

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.

Volltext und
andere Links
PDF (2490125 Bytes)
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Algorithmik
BetreuerFunke, Prof. Stafen; Seybold, Martin
Eingabedatum1. August 2018
   Publ. Institut   Publ. Informatik