05 Fakultät Informatik, Elektrotechnik und Informationstechnik
Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6
Browse
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 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 Circuit complexity of group theoretic problems(2021) Weiß, Armin; Diekert, Volker (Prof. Dr. rer. nat.)In dieser kumulativen Habilitationsschrift werden sechs Arbeiten zum Thema "Schaltkreiskomplexität von Gruppentheoretischen Problemen" zusammengefasst. An vorderster Stelle steht hierbei das Wortproblem: Gegeben ein Wort über den Erzeugern einer Gruppe, ist die Frage, ob das Wort das Einselement der Gruppe darstellt. Daneben werden noch weitere Probleme, wie das Konjugationsproblem, das Power-Wortproblem (wie das Wortproblem, aber die Eingabe wird in komprimierter Form gegeben) und das Lösen von Gleichungen betrachtet. Die meisten der hier zusammengefassten Arbeiten betrachten die genannten Probleme für spezielle Klassen von Gruppen und klassifizieren deren Komplexität mit Methoden der Schaltkreiskomplexität. Eine Ausnahme bildet die letzte Arbeit zum Thema Gleichungen: hier liegt der Zusammenhang zur Schaltkreiskomplexität darin, dass sich das Erfüllbarkeitsproblem für Gleichungen in endlichen auslösbaren Gruppen ähnlich verhält wie das Erfüllbarkeitsproblem für CC^0 Schaltkreise.Item 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, StefanWe 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.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).Item Open Access Sublinear search spaces for shortest path planning in grid and road networks(2021) Blum, Johannes; Funke, Stefan; Storandt, SabineShortest path planning is a fundamental building block in many applications. Hence developing efficient methods for computing shortest paths in, e.g., road or grid networks is an important challenge. The most successful techniques for fast query answering rely on preprocessing. However, for many of these techniques it is not fully understood why they perform so remarkably well, and theoretical justification for the empirical results is missing. An attempt to explain the excellent practical performance of preprocessing based techniques on road networks (as transit nodes, hub labels, or contraction hierarchies) in a sound theoretical way are parametrized analyses, e.g., considering the highway dimension or skeleton dimension of a graph. Still, these parameters may be large in case the network contains grid-like substructures - which inarguably is the case for real-world road networks around the globe. In this paper, we use the very intuitive notion of bounded growth graphs to describe road networks and also grid graphs. We show that this model suffices to prove sublinear search spaces for the three above mentioned state-of-the-art shortest path planning techniques. Furthermore, our preprocessing methods are close to the ones used in practice and only require expected polynomial time.Item Open Access Computing shortest path distances based on cluster-pairs(2021) Epple, LukasIn this thesis we present a new lookup based shortest path distance computation scheme. Like many other lookup based schemes, this new approach consists of two stages, a preprocessing and a query stage. After the properties, which need to be met by the results of the preprocessing, are formally defined, we propose different preprocessing procedures as well as procedures which are able to use those results to calculate shortest path distances. The proposed new query procedure is able to decide whether a given query can be answered when the preprocessed data is incomplete. This makes it possible to prune the preprocessed data according to arbitrary memory constraints, while a speed up of orders of magnitude in comparison to conventional techniques can be achieved.Item Open Access OpenStreetMap risk maps(2021) Lindemann, PatrickMilitärische Strategiespiele wie das beliebte rundenbasierte Brettspiel „Risiko“ von Hasbro bieten die Möglichkeit, spielbare Karten zu erstellen, die reales Kartenmaterial verwenden, da Spieler gerne solche Spiele auf Spielbrettern spielen möchten, die den realen Karten möglichst nahe kommen. Unter Verwendung der frei verfügbaren und kontinuierlich gepflegten Geodaten des OpenStreetMap-Projekts haben wir ein MapMaker-Tool entwickelt, das den Prozess der Kartenerstellung weitgehend automatisiert. Wir verwenden verschiedene Algorithmen, um die administrativen Grenzen, die aus den geografischen Quelldaten extrahiert werden, zu komprimieren und zusammenzusetzen, und sammeln zusätzliche Metadaten, einschließlich der Aggregation von angrenzenden Gebieten und Hierarchien für Bonusebenen, um eine vollständig spielbare Karte zu erstellen. Zu guter Letzt nutzen wir das Online-Strategiespiel Warzone, um unsere Arbeit mit echten Spielern zu testen und zu bewerten.