05 Fakultät Informatik, Elektrotechnik und Informationstechnik
Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6
Browse
20 results
Search Results
Item Open Access Performance measurements for personalizable route planning for uncorrelated edge costs(2021) Bühler, FelixNowadays, ordinary route planners compute paths by choosing the shortest or fastest route. However, there exist additional metrics from which users with varying preferences could benefit. Personalized route planning offers the possibility to combine different metrics with personal preferences. Nevertheless, personalized route planning has mainly been tested with correlated metrics. But when including uncorrelated metrics, the computing time increases significantly. Previous work found that the speedup technique “Customizable Route Planning” can lead to feasible speedups for single metric calculations. Thus, in this work, we investigate how this speedup technique for Dijkstra improves the query performances of “Personalizable Route Planning” compared to “Personalizable Contraction Hierarchies”. Furthermore, we study the performances on uncorrelated metrics. We introduce a graph structure to compare the personalized speedup techniques “Personalizable Contraction Hierarchies”, “Personalizable Customizable Route Planning” and “Personalizable Route Planning”. Three graph partitioning algorithms have been implemented to realize “Customizable Route Planning”: K-means, Gonzales, and Merge. Our experiments show that Merge works well in combination with “Personalizable Contraction Hierarchies” preprocessing. We found that “Personalizable Customizable Route Planning” is a good alternative, as it uses much fewer edges for finding the costs of the shortest path. For uncorrelated metrics, “Personalizable Customizable Route Planning” and “Personalizable Route Planning” achieved speedups higher than “Personalizable Contraction Hierarchies”. Our contribution comprises a novel graph structure for comparing different Dijkstra variants. With our experiments, we provide a deeper understanding of the personalized route planning problem. Additionally, we propose improvements for “Personalizable Contraction Hierarchies” for less contracted graphs with uncorrelated metrics.Item Open Access Generierung und Abdeckung repräsentativer Pfadmengen in Straßennetzwerken(2022) Berner, LukasFür die Suche nach kürzesten Pfaden in sehr großen Graphen wurden verschiedene Beschleunigungstechniken, wie z.B. Contraction Hierarchies, Hub-Labels oder Transit Node Routing, entwickelt. Um optimale Anfragezeiten und Speicherverbrauch zu erreichen, benötigen viele Beschleunigungstechniken eine Menge wichtiger Knoten. In dieser Arbeit wird eine Methode zur Berechnung wichtiger Knoten eines Graphen vorgestellt. Um diese Knoten zu finden, wird auf einer repräsentativen Pfadmenge ein Hitting Set Problem mit einem Greedy-Algorithmus gelöst. Die repräsentative Pfadmenge, die möglichst unterschiedliche kürzeste Pfade des Graphen enthalten soll, wird mit einer well-separated pair decomposition und einem Quadtree berechnet. Das Verfahren wurde mit dem deutschen Straßennetzwerk (25M Knoten) getestet und liefert hier einige tausend wichtige Knoten, mit denen bereits etwa 99,9 % aller kürzesten Pfade im Graph abgedeckt sind.Item Open Access Verbotsmuster für Logik mit zwei Variablen über endlichen und unendlichen Wörtern(2023) Heindl, AmelieDie Varietät DA, die mit der Logik erster Stufe über zwei Variablen übereinstimmt, bildet das höchste Level der Trotter-Weil-Hierarchie. Varietäten in dieser Hierachie können algebraisch über l-Gleichungen charakterisiert werden und haben teilweise äquivalente Klassen in der Quanto- renalternierungshierarchie innerhalb FO2. Um Sprachen mit diesen Klassen in Verbindung zu bringen, ist es möglich, das syntaktische Monoid auszurechnen und für alle möglichen Belegungen die l-Gleichung zu überprüfen. Aus komplexitätstheoretischer Sicht ist dieser Ansatz aufwändig und diese Arbeit befasst sich mit Kriterien, mit denen man die gesuchte Verbindung direkt auf den Automaten der Sprachen prüfen kann. Das zentrale Konzept stellen dabei Verbotsmuster dar. In dieser Arbeit wird eine Definition für Verbotsmuster bei nicht notwendigerweise minimalen DEAs und CMAs gegeben. Damit werden explizite Verbotsmuster für Sprachen über endlichen Wörtern für die Varietäten an den Enden der Hierarchie konstruiert und ein allgemeines Schema für die inneren Level angepasst. Aus diesen Mustern werden Verbotsmuster für fin-syntaktische Monoide von Sprachen über unendlichen Wörtern abgeleitet. Zusammen mit einem Verbotsmus- ter, das die Zugehörigkeit zu DA für inf-syntaktische Monoide entscheidet, lässt sich damit die Trotter-Weil-Hierarchie vollständig für DEAs und CMAs charakterisieren. Für alle konstruierten Verbotsmuster werden NL- und P-Algorithmen erstellt, die Automaten auf das Enthalten dieser Verbotsmuster prüfen. Dies beinhaltet sowohl Algorithmen, bei denen ein festes Verbotsmuster gegeben ist, als auch Algorithmen, bei denen es Teil der Eingabe ist. Für die Varietäten der Trotter-Weil-Hierarchie existieren auch Verbotsmuster mit Teilwortbeziehungen, die von Henriksson und Kufleitner definiert wurden. Die beiden Verbotsmusterarten werden in dieser Arbeit verglichen. Dabei werden insbesondere die Größen der Muster, die Komplexitätsschranken der Algorithmen und die gefundenen Zeugen berechnet. Es ergibt sich ein Größenvorteil der Teilwortmuster gegenüber den Faktormustern bei vergleichbaren Komplexitäten der Algorithmen.Item Open Access Simulation and analysis of complex dynamics in a low-dimensional model of a vibration-machine(2021) Roggenbuck, KayIn the past decades, the importance of discontinuous piecewise-smooth models has been well-established. So far, the dynamics of such models are mostly analyzed based on functions with a single point of discontinuity. This class of functions is well-investigated in the literature and many theoretical results are known. Even though many physical phenomena can be described by this class, for more complex systems, a single point of discontinuity is not sufficient. In this thesis, this theory is extended by the analysis of a map in which the number of discontinuities varies based on different parameters. It is shown that this map does for integer-valued parameters result in clear dynamics, e.g. a sausage-shaped period-adding cascade. Even though these structures are already known in the literature, the understanding of its dynamics is key for the analysis of the structures for a more generalized range of parameter values. For example, for real-valued parameters the map show a much more complex structure consisting of a combination of period-adding and period-incrementing with different coexistence scenarios. Furthermore, it is shown that the iteratively increasing of a parameter related to the number of discontinuities destroys the sausage-shaped structure and transforms it for the next higher integer value to a more complex sausage-shaped structure. It is investigated how this structure is destroyed and how it evolves in the intermediate steps. Additionally, in this new structure an example configuration of the model is found where well-established results from a map with one discontinuity can not be applied.Item Open Access Integration of CH/HL-based route planning in OSCAR(2020) Makolli, SokolEfficient and fast shortest path routing on road networks is required to meet the demands of millions of users every day. In this work we document an implementation, which combines two popular speed up techniques. The results show that with little space overhead a speed up of one order of magnitude to conventional techniques is achievable, while also giving the choice of using either disk or RAM storage. The routing application is also integrated into the search engine OSCAR, which then allows for interactive exploration of locations along the route.Item Open Access Learning metrics for balancing load in street-networks(2020) Parga Cacheiro, DominicEspecially in daily rush-hour-scenarios, a street-network requires enough capacity to support the amount of drivers. On the other hand, a street-network of too much capacity would be inefficient outside of rush-hour-scenarios. Hence, the overload during rush-hour should be spreaded over the network to reduce the impact of the overload (\eg\ traffic-jams). To improve the distribution of routes, alternative routes in multicriteria settings are computed. To support multicriteria settings, Dijkstra's algorithm is combined with personalized routing. Here, these multicriteria or multiple metrics, \eg\ travel-time or travel-distance, can be reduced to scalars by applying preferences to them. Resulting routes or paths are called personalized paths. However, many previous approaches for computing alternative routes need too much parameter-tuning or simply lack in their computational complexity, their needed runtime or in the diversity of their found routes. Therefore, this thesis presents a combination of enumerating personalized paths with the creation of a new penalizing metric. The goal is to compensate other popular metrics with this new metric, which then improves the spread of many routes in the network. This new metric can be processed by every routing-algorithm, that is capable of dealing with multicriteria-routes. By enumerating personalized paths with this new penalization, found routes can be distributed successfully over the network. In addition, user-provided tolerances for preferred metrics are hold. In the end, some experiments on street-networks from OpenStreetMap are presented. Here, results are compared between routes from Dijkstra (with personalized routing) and the enumeration of personalized routes. To speed the route-queries up significantly, the underlying graphs of the networks are contracted via contraction-hierarchies before the searches happen. Here, the contraction is realized by a linear program to improve the performance with multicriteria contractions.Item Open Access Anwendung der Well-Separated Pair Decomposition auf Sichtbarkeitsgraphen(2020) Owens, NiklasBisherige Ansätze zur Berechnung von Pfaden zwischen zwei Punkten mit mini- maler euklidischer Länge in einer Umgebung mit unpassierbaren Hindernissen basieren oft auf der Konstruktion des vollständigen Sichtbarkeitsgraphen um auf diesem Routing-Algorithmen auszuführen. Problematisch an diesen Verfahren ist zum einen die hohe Berechnungszeit des vollständigen Sichtbarkeitsgraphen, zum anderen, dass die Komplexität des Sichtbarkeitsgraphen in O(n2) liegt. Um dies zu vermeiden, befasst sich diese Arbeit mit der Entwicklung eines Verfahrens zur Konstruktion von Spannern für Sichtbarkeitsgraphen, auf denen kürzeste Pfade approximiert werden können. Anhand experimenteller Vergleiche mit einem naiven Algorithmus hat sich gezeigt, dass die Spannerkonstruktion deutlich schneller ist als die des vollständigen Sichtbarkeitsgraphen, wobei die Läge der approximierten Pfade im Durchschnitt nur geringfügig von der Länge der tatsächlich kürzesten Pfade abweicht.Item Open Access Sichtbarkeit in triangulierten planaren Unterteilungen(2023) Larche, DominikIn dieser Arbeit wird ein neuer Algorithmus für eine effiziente Berechnung der sichtbaren Hindernisecken in einem euklidischen Raum mit Hindernissen vorgestellt. Dieser Algorithmus wird anschließend dazu vewendet, einerseits den vollständigen Sichtbarkeitsgraphen und andererseits mithilfe eines Dijkstra-basierten Verfahrens den kürzesten Pfad in einem euklidischen Raum mit Hindernissen zu ermitteln. Die hier vorgestellten Algorithmen werden, im Gegensatz zu den Ansätzen aus früheren Papern, auf einem klassischen Rechner implementiert und ihre Laufzeiten werden mit denen der naiven Verfahren verglichen.Item Open Access The power word problem in graph groups(2021) Stober, FlorianThis thesis studies the complexity of the power word problem in graph groups. The power word problem is a variant of the word problem, where the input is a power word. A power word is a compact representation of a word. It may contain powers p^x, where p is a finite word and x is a binary encoded integer. A graph group, also known as right-angled Artin group or partially commutative group is a free group augmented with commutation relations. We show that the power word problem in graph groups can be decided in polynomial time, and more precisely it is AC^0-Turing-reducible to the word problem of the free group with two generators F_2. Being a generalization of graph groups, we also look into the power word problem in graph products. The power word problem in a fixed graph product is AC^0-Turing-reducible to the word problem of the free group F_2 and the power word problem of the base groups. Furthermore, we look into the uniform power word problem in a graph product, where the dependence graph and the base groups are part of the input. Given a class of finitely generated groups C, the uniform power word problem in a graph product is CL-Turing-reducible to the word problem in the free group F_2 and the uniform power word problem in C. Finally, we show that as a consequence of our results on the power word problem the uniform knapsack problem in graph groups is NP-complete.Item Open Access Over-the-web retrieval and visualization of massive trajectory sets(2021) Baur, LukasAs the number of cost-effective GPS-supporting devices continues to increase tremendously, the number of recorded trajectories, i.e., measured sequences in time and space, explodes. The enormous potential of this data in terms of information retrieval data mining analysis of various kinds requires advanced storage and retrieval solutions. In [25], Funke et al. presented a data structure Pathfinder (PF) based on a state-of-the-art speed-up technique for shortest path planning allowing for efficient trajectory compression and rather complex query answering. Since PF results are returned in compressed form by default and their complete decompression is only possible with the help of the internal data structure, a separation of a retrieval server and lightweight clients is nontrivial. Even more problematic is the amount of data produced by naively decompressing large queries: transferring the fully unpacked paths is neither meaningful nor feasible taking usual response waiting times into consideration. This work closes the gap by presenting partially decompression and postprocessing methods based on aggregation, pruning, filtering, simplification, and batching in order to accomplish predefined use case goals. The presented methods are theoretically examined, tested on different real-world and synthetic datasets consisting of up to 10 000 000 trajectories, and critically reviewed with regard to applicability. In addition, for the special use case that relies exclusively on spatio- temporally independent queries, a Pathfinder-based static tiling server was included which could be conceptually extended to online tiling for query answering as a prototype showed. [25] S. Funke, T. Rupp, A. Nusser, S. Storandt. “PATHFINDER: Storage and Indexing of Massive Trajectory Sets”. In: Proceedings of the 16th International Symposium on Spatial and Temporal Databases. SSTD ’19. Vienna, Austria: Association for Computing Machinery, 2019, pp. 90–99. isbn: 9781450362801. doi: 10 . 1145 / 3340964 . 3340978 . url: https : //doi.org/10.1145/3340964.3340978 (cit. on pp. 3, 15, 18, 21, 22, 25–27).