Browsing by Author "Rupp, Tobias"

Now showing 1 - 4 of 4

Open Access
Contraction Hierarchies für kontinuierliche Graphsimplifizierung mit Qualitätsgarantien
(2016) Rupp, Tobias
Moderne Navigationsdienste können kürzeste Pfade berechnen und diese dann auf Straßenkarten anzeigen. Als zugrunde liegende Datenstruktur für beide Aufgaben kann eine Contraction Hierarchy verwendet werden. Ursprünglich waren Contraction Hierarchies dazu konzipiert, die Suche nach kürzesten Pfaden zu beschleunigen. In dieser Arbeit wurde untersucht, wie sich Contraction Hierarchies aufbauen lassen, sodass sie sich besser für kontinuierlich vereinfachte Darstellungen eignen. Dazu sollten vor allem die groben Straßenverläufe erhalten bleiben und topologische Inkonsistenzen wie Überschneidungen vermieden werden. Diese Anforderungen wurden formalisiert und in heuristischen Vereinfachungsalgorithmen zum Aufbau von Contraction Hierarchies umgesetzt. Für kleine Eingaben wurden mithilfe ganzzahliger linearer Programme garantiert optimale Lösungen berechnet. Damit konnten in empirischen Vergleichen auf dem Deutschlandgraphen Qualitätsgewinne nahe dem Optimum für vereinfachte Darstellungen von Contraction Hierarchies nachgewiesen werden. Außerdem mussten keine längeren Berechnungszeiten für kürzeste Pfade hingenommen werden.
Open Access
Contraction hierarchies: theory and applications
(2022) Rupp, Tobias; Funke, Stefan (Prof. Dr.)
Contraction Hierarchies describes a technique that enormously accelerates the calculation of shortest paths on road networks in practice. In the first part of this thesis, this acceleration is analyzed theoretically. For this purpose, we introduce the graph family of lightheaded grids. On one hand, light-headed grids have realistic properties as planarity and occur in real world road networks. On the other hand, their generic structure makes them suitable for theoretical analysis. We prove a lower bound Ω( n) for the average query phase of contraction hierarchies on lightheaded grids. At the cost of more disk space, hub labels is another technique which enables even quicker answering of shortest path queries than contraction hierarchies. For hub labels, we prove that the average hub label size of a node is in Ω( n) on lightheaded grids with the same idea as in the previous proof. Then we develop this proof idea even further into a schema which is able to compute instance-based lower bounds for both contraction hierarchies and hub labels on any arbitrary given graph. For some graph families such as balanced ternary trees, we show that this schema yields tight bounds, i.e. the lower bounds matches a concrete contraction hierarchy and hub labeling. In previous contributions concerning upper bounds, it was believed that it is meaningful to consider only explored nodes to upper bound the query time. For example, it was proven for one proposed contraction strategy based on separators, that during query time of contraction hierarchies, only sublinear many nodes are explored on average for a wide family of graphs which includes lightheaded grids. For lightheaded grids, we prove that this strategy yields linear many edges to be explored on average, therefore showing that considering only the number of explored nodes is not sufficient. We also show that it is not the contraction hierarchy framework which is necessarily flawed but the proposed strategy by giving another strategy for which only sublinear many edges need to be explored on average. In the second part of this thesis, contraction hierarchies are adapted to fit other purposes than answering short paths queries only. First, we show how trajectories, i.e. movement of individuals on the road network, can be stored efficiently if the contraction hierarchy data structure is present. When describing the compression process of raw trajectory data, we also prove that the compressed presentation is unique. Having the data compressed will also be beneficial for answering retrieval queries which ask for all trajectories intersecting a given space-time cube. We describe how to augment the contraction hierarchy data structure further to answer such queries quicker than state-of-the-art approaches. Interestingly, contraction hierarchies can also be instrumentalized to visualize graph simplifications 9as it was already demonstrated in the URAN framework. However, the URAN framework had some shortcomings which we address. We ensure that a simplified graph retains its original silhouette better and avoids some topological inconsistencies. Moreover, we apply similar techniques to visualize trajectory data sets within our framework PATHFINDERVIS which is also able to provide different flavors of visualization including heat-map based ones.
Open Access
A lower bound for the query phase of contraction hierarchies and hub labels and a provably optimal instance-based schema
(2021) Rupp, Tobias; Funke, Stefan
We prove a Ω(√n) lower bound on the query time for contraction hierarchies (CH) as well as hub labels, two popular speed-up techniques for shortest path routing. Our construction is based on a graph family not too far from subgraphs that occur in real-world road networks, in particular, it is planar and has a bounded degree. Additionally, we borrow ideas from our lower bound proof to come up with instance-based lower bounds for concrete road network instances of moderate size, reaching up to 96% of an upper bound given by a constructed CH. For a variant of our instance-based schema applied to some special graph classes, we can even show matching upper and lower bounds.
Open Access
Verbotsmuster bei deterministischen endlichen Automaten in der Trotter-Weil-Hierarchie
(2013) Rupp, Tobias
Die Klasse DA von endlichen Monoiden besitzt eine Vielzahl an Charakterisierungen logischer, kombinatorischer und algebraischer Art. Unter anderem bildet DA eine sogenannte Varietät. Um die Struktur der Untervarietäten von DA zu untersuchen, betrachteten Trotter und Weil den Schnitt mit idempotenten Halbgruppen. Da deren Hierarchie bereits bekannt war, führte dies zu einer neuen Varietätenhierarchie innerhalb von DA, der Trotter-Weil-Hierarchie. Überdies konnten für diese Varietäten algebraische Charakterisierungen angegeben werden, die Entscheidbarkeit ermöglichten. Falls nun eine Sprache in der Form eines deterministischen endlichen Automaten gegeben ist, soll effizient entschieden werden können, ob das syntaktisches Monoid in einer gegebenen Varietät der Trotter-Weil-Hierarchie liegt. In dieser Bachelorarbeit werden unter Verwendung von Verbotsmustern entsprechende Entscheidungsalgorithmen der Komplexitätsklassen NL und P konstruiert. Verbotsmuster bezeichnen hierbei Graphkonfigurationen, die im Automatengraph nicht vorkommen dürfen.