05 Fakultät Informatik, Elektrotechnik und Informationstechnik
Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6
Browse
6 results
Search Results
Item 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.Item Open Access OSCAR: a textual and spatial exploratory search engine for OpenStreetMap data(2020) Bahrdt, Daniel; Funke, Stefan (Prof. Dr.)Item Open Access Personalized route planning : on finding your way in theory and practice(2022) Ihle, Florian Benjamin; Funke, Stefan (Prof. Dr.)Personalisierung ist ein wichtiger Trend in der heutigen digitalen Welt. Im Bereich der Routenplanung hatte dieser jedoch noch keine starken Auswirkungen. Diese Dissertation beschäftigt sich mit dem multikriteriellen Routenplanungsansatz, der “personalized route planning model” genannt wird. Das Modell optimiert Konvexkombinationen von Routenplanungskriterien wie z.B. Reisezeit, Distanz oder Straßentyp und berechnet unterschiedliche Routen basierend auf den Präferenzen des Nutzers. Wir nennen die optimalen Pfade dieses Modells personalisierte Pfade. Das Angeben solcher Präferenzen ist keine einfache Aufgabe für einen Nutzer. Daher haben wir uns im praktischen Teil unserer Forschung auf Anwendungen konzentriert, die die Präferenzen im Backend verarbeiten ohne den Nutzer mit ihnen zu konfrontieren. Wir stellen drei praxisorientierte Anwendung und eine theoretische Analyse des Models vor. Für jede der Anwendungen entwickelten wir effiziente Algorithmen und verifizierten die Qualität und Laufzeit experimentell. Die erste Anwendung findet große Mengen von Alterantivrouten, die nicht zu sehr überlappen. Dazu entwickeln wir einen Algorithmus, der alle personalisierten Pfade aufzählen kann. Dieser wird dann erweitert um optional das Berechnen von Pfaden zu vermeiden, die zusätzliche Optimalitätskriterien nicht erfüllen. Darüber hinaus zeigen wir ‘erfundene’ Routenplanungskriterien, die die Ergebnisse noch weiter diversifizieren. In unseren Experimenten beobachteten wir große Mengen an sinnvollen Alternativrouten. Im Gegensatz zur ersten Anwendung sind die nächsten beiden Anwendung nicht an Endnutzer gerichtet, sondern dienen zum Lernen aus bestehenden Trajektorien. Die zweite Anwendung identifiziert Zwischenziele in Trajektorien. Wir nehmen an, dass Fahrer auf längeren Fahrten mit mehreren Zielen personalisierte Pfade zwischen den einzelnen Zielen wählen. Daher verwenden wir einen Trajektoriensegmentierungsansatz, der die Trajektorien in personalisierte Pfade aufteilt. Unser Ansatz konnte ca. 60% aller bekannten Zwischenziele in einem echt Welt Datensatz exakt erkennen und 90% waren sehr nahe an den errechneten Zwischenzielen. Unsere letzte Anwendung hat das Ziel Trajektorien nach Präferenzen zu clustern. Hier ist die Idee eine Menge an Trajektorien durch eine kleine Menge Präferenzen zu erklären, so dass jede Trajektorie für eine der Präferenzen optimal ist. Das erlaubt es wichtige Präferenzen für einzelne Fahrer zu finden oder eine Menge von Fahrern zu kategorisieren. Wir berechnen den Präferenzbereich für alle Trajektorien und lösen eine darauf basierende geometrische “Hitting Set” Instanz. Obwohl beide Schritte im schlimmsten Fall teuer zu berechnen sind, stellten wir fest, dass der gesamte Prozess häufig in Sekunden bis Minuten berechnet werden kann für Instanzen mit tausenden Trajektorien. Im letzten Teil der Dissertation analysieren wir wie viele personalisierte Pfade es abhängig von der Graphgröße zwischen zwei Knoten geben kann. Unsere Analyse basiert auf zwei speziellen Graphfamilien und wird dann auf alle Graphen generalisiert. Wir beweisen, dass die Anzahl der personalsierten Pfade subexponentiell in der Graphgröße und exponentiell in der Zahl der Routenplanungskriterien ist.Item Open Access Automaton structures : decision problems and structure theory(2020) Wächter, Jan Philipp; Diekert, Volker (Prof. Dr.)This thesis is devoted to the class of automaton groups and semigroups, which has gained a reputation of containing groups and semigroups with special algebraic properties that are hard to find elsewhere. Both automaton groups and semigroups are studied from a structural and an algorithmic perspective. We motivate the use of partial automata as generating objects for algebraic structures and compare them to their complete counterparts. Additionally, we give further examples of semigroups that cannot be generated by finite automata and show that every inverse automaton semigroup is generated by a partial, invertible automaton. Moreover, we study the finite and infinite orbits of ω-words under the action induced by an automaton. Here, our main result is that every infinite automaton semigroup admits an ω-word with an infinite orbit. We apply these structural results algorithmically and show that the word problem for automaton groups and semigroups is PSpace-complete. Furthermore, we investigate a decision problem related to the freeness of automaton groups and semigroups: we show that it is undecidable whether a given automaton admits a non-trivial state sequences that acts trivially and we use this problem for further reductions. Afterwards, we strengthen Gillibert’s result on the undecidability of the finiteness problem for automaton semigroups and give a partial solution for the group case of the same problem. Finally, we consider algorithmic questions about increasing the orbits of finite words and apply these results to show that, among others, the finiteness problem for (subgroups of) automaton groups of bounded activity is decidable.Item Open Access Improved algorithms for map rendering and route planning(2020) Mendel, Thomas; Funke, Stefan (Prof. Dr.-Ing.)In dieser Arbeit werden verschiedene Teilbereiche der Kartendarstellung und der Wegefindung betrachtet. Der erste Teil beschäftigt sich mit Grenzvereinfachung und Gebietsbeschriftung. Der zweite Teil stellt ein beschleunigtes Verfahren zur Berechnung kürzester Wege vor.Item Open Access Labeling interactive maps(2020) Krumpe, Filip; Funke, Stefan (Prof. Dr.)Navigationssysteme, beziehungsweise digitale Kartenapps, haben sich zu alltäglichen Begleitern entwickelt. Waren digitale Karten vor einem Jahrzehnt ein wertvolles Gut - Updates für Navigationssysteme wurden für viel Geld verkauft- sind sie heute durch die Verbreitung von Google Maps und Co. eine Selbstverständlichkeit. Neben der Verfügbarkeit und der Möglichkeit einfacher Updates, ermöglichen digitale Karten eine einfache, intuitive Interaktion. Das Zoomen, Verschieben und Drehen des Kartenausschnitts zum Erkunden von Details und der Ausrichtung in Blickrichtung des Nutzers, sind wohlbekannte Funktionen. Letzteres ist vor allem bei Navigationssystemen zentral. Dort wird die Kartenausrichtung generell in Fortbewegungsrichtung gewählt. Insbesondere für die Darstellung von Kartenbeschriftung, stellen diese Möglichkeiten eine Herausforderung dar. In der vorliegende Arbeit wird ein Konzept zur Gestaltung von Beschriftungen in interaktiven Karten, die stufenloses Zoomen, Verschieben und Rotieren des Kartenausschnitts ermöglichen, vorgestellt. Dabei wird insbesondere die Beschriftung von sogenannten ”Points of Interest” - also zu beschriftenden Punkten - thematisiert. Derartige Beschriftungen sind gewöhnlich horizontal ausgerichtet und überlappen sich somit tendenziell bei der Kartenrotation. Vor allem beim Zoomen der Karte sind verschiedene Konsistenzkriterien zu beachten - so soll beispielsweise eine Beschriftung während eines kontinuierlichen Zoomens nicht mehrfach hinzugefügt und wieder entfernt werden. Außerdem sollen Beschriftungen von wichtigeren Punkten länger sichtbar sein, als solche von weniger wichtigen Punkten. Bei der Beschriftung von Gebieten gilt, dass sich die Beschriftung im Gebiet befinden und die grobe Form des Gebiets adaptieren soll. Um letzteres zu erreichen, darf die Beschriftung entlang eines Kreisbogens gebogen sein. Rotation ist in diesem Szenario einfach - die Beschriftung muss lediglich in ihrer Ausrightung umgekehrt werden, sodass sie nicht auf dem Kopf steht. Beim Zoomen des Kartenausschnitts sollten Gebiete als Ganzes oder ihre Untergebiete beschriftet werden, abhängig von der Kartenskala der Gebietsbeschriftung. Für der Beschriftung von Punkten werden sogenannte ”Disk-Label” eingeführt. Bei diesen wird für jede Beschriftung ein kreisförmiger Bereich um den zu beschriftenden Punkt reserviert. Die Beschriftung des Punkts bleibt in beliebigen Ausrichtungen der Karte vollständig in diesem Bereich enthalten. Indem als Beschriftung in einer beliebigen Kartenskala eine überschneidungsfreie Untermenge der ”Disk-Label” gewählt wird, ist die lesbare Darstellung bei Rotation gewährleistet. Beim Herauszoomen aus dem Kartenausschnitt, werden die Beschriftungen bei konstanter Größe beibehalten. Entsprechend wachsen die zugehörigen Disks relativ zur Karte - entsprechend schrumpfen die Distanzen zwischen den Disks. Bei fortschreitendem Zoomen, kommt es zu Berührungen der Disks. Dabei muss eine der beteiligten Beschriftungen muss entfernt, um bei weiterem Zoomen die überschneidungsfreiheit zu erhalten. Wird der entsprechende Zoomprozess von ”unendlich 107weit hineingezoomt” zu ”unendlich weit herausgezoomt” betrachtet, ergibt sich eine sogenannte Eliminationssequenz der Beschriftungen. Diese kann für einen Datensatz im Voraus berechnet werden und ermöglicht dann eine einfache, effiziente Ableitung einer Kartenbeschriftung für ein gegebenes Darstellungszenario. Das Problem der Berechnung der Eliminationssequenzen kann verallgemeinert in einem d-dimensionalen Hyperraum betrachtet werden. Entsprechend der Disks in 2D, wachsen d-dimensionalen Hyperbälle. Eine Eiminationssequenz ist dabei nicht eindeutig - kollidieren Bälle der selben Wichtigkeit, ist die Entscheidung welcher der beiden Bälle eliminiert wird, essentiell für den weiteren Verlauf der Sequenz. Das Ziel ist die Berechnung einer optimalen Sequenz, in der die Summe aller Eliminationszeitpunkte maximiert wird. Es wird gezeit, dass die Berechnung einer solchen optimalen Sequenz N P − hart ist. Für ein vereinfachtes Szenario - in welchem die Sequenz eindeutig ist - wird ein effizientes Berechnungsverfahren vorgestellt und analysiert. Dieses Verfahren hängt stark von einer effizienten Methode zur Berechnung des nächsten Nachbarn sowie der Suche nach Punkten mit einer maximalen Distanz zu einem gegebenen Punkt ab. Je nach Szenario können diese Operationen effizienter oder weniger effizient gelöst werden. Für 2D und für höhere Dimmensionen werden zwei verschiedene theoretische Laufzeitschranken bewiesen. Für die praktische Beschriftung von digitalen Karten, werden Punkte auf einem virtuellen Globus betrachtet. Eine Berechnung der Sequenz für 13 Millionen Punkte ist auf einem herkömmlichen Computer in etwa 15 Minuten möglich. Das ursprüngliche, unvereinfachte Problem kann mittels eines Mixed-Integer Linearen Programms für wenige Punkte exakt gelöst werden. Allerdings nur mit erheblichem Rechen- und Speicheraufwand. Eine gute Approximation der optimalen Sequenz bieten Heuristiken. Mittels dieser kann der vorgestellte Algorithmus für das vereinfachte Szenario Lösungen für das unvereinfachte Problem berechnen. In der Güte liegen die Heuristiken bei 5% − 10% unter dem Optimum. Bei Berechnungszeiten von 15 − 20 Minuten auf einem herkömmlichen Computer. Eine Gebietsbeschriftung liegt vollständig innerhalb des Gebiets und ahmt die Form des Gebiets nach, indem sie entlang eines Kreisbogens plaziert ist. Für eine gute Beschriftung ist eine entsprechende Platzierung gesucht, welche die Größe der Beschriftung maximiert. Abhängig davon kann eine maximale und minimale Kartenskala berechnet werden, bei welcher die Beschriftung lesbar dargestellt werden kann. Entsprechend kann das Gebiet bei größeren Skalen in einer weiteren Verfeinerung dargestellt, oder bei kleineren Skalen durch eine Punkt-Beschriftung oder die Darstellung eines umfassenden Gebiets ersetzt werden. Für die Berechnung einer solchen guten Beschriftung wird in der vorliegenden Arbeit ein effizienter Algorithmus vorgestellt. Dieser basiert auf einem Algorithmus von 2001, von M. Barrault in [Mat01] publiziert. Durch verschiedene Optimierungen kann diese Berechnung auf Quasi-Echtzeit verbessert werden.