Incremental weak Fréchet map-matching

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.

Viele geografische Informationssysteme haben die Aufgabe Positionsdaten in Form von Verläufen auf eine gegebene Karte abzubilden, das sogenannte Map-Matching. Eine Kategorie von Ansätzen zur Lösung dieser Problemstellung sind geometrische Algorithmen, die sich der Fréchet Metrik bedienen. Diese Verfahren nutzen entweder eine Kombination von Parameter- und Tiefensuche oder eine modifizierte Variante des Dijkstra-Algorithmus, um den besten Match zu finden. In dieser Arbeit wird ein Algorithmus auf Basis der Weak Fréchet Metrik entwickelt, welcher diese Techniken umgeht, um eine Beschleunigung der Match-Berechnung zu erreichen. Der vorgestellten Algorithmus ermöglicht eine einfache Parallelisierung aufgrund seines inkrementellen Vorgehens. Die Evaluierung des vorgestellten Algorithmus wurde auf Basis der theoretischen Laufzeiten sowie einer experimentellen Gegenüberstellung des Ansatzes von Wenk et al.[WSP06] vollzogen, zeigte jedoch nur bei starker Parallelisierung positive Ergebnisse.