Browsing by Author "Eisner, Jochen"

Now showing 1 - 1 of 1

Open Access
Shortest path speed up techniques : lower bounds and applications
(2013) Eisner, Jochen; Funke, Stefan (Prof. Dr.)
The widespread proliferation of portable hand held computing devices in the form of mobile phones, rivaling 6 year old desktop computers in raw computational power and outclassing them in terms of communication interfaces and interoperability, gave rise to a plethora of new geospatial applications and services. One of the many roles a modern mobile phone can provide, is the complete substitution of printed maps with added functionality as navigation aid, for self localization, or - with more semantic back-end information - complex routing queries all around the world. With the computer-based compilation of the majority of the worlds' road networks, which are freely available to everyone in the form of OpenStreetMap, vast geospatial databases are to our disposal today. One of the most fundamental questions in such a network is to compute a shortest (or quickest) path between two designated points. This problem was solved by Dijkstra in 1959 in a provably optimal way, but his algorithm, although very elegant and simple in design, does not scale well on continent sized road graphs. Therefore a multitude of alternative approaches for the single-source-single-target shortest path problem and more complicated flavors were devised in the last decade. The motivation for highly efficient algorithms in this field is twofold. On the one hand they enable a real time user experience on a mobile phone, even for complex tasks, on the other hand these approaches scale well when a server back-end is employed, whose task is to server a large number of mobile agents. If used in combination these techniques enable us to compute different shortest path related problems in the order of ten milliseconds on the complete road network of Europe. This constitutes a speedup of more than three magnitudes compared to Dijkstra's approach. This work consists of three main parts, each addressing an exemplary problem in the field of geospatial application which are outlined in the following sections. - Transit Node Constructions Revisited In the first part we reconsider the concept of transit nodes as introduced by Bast et al. Transit nodes are an offline speed up technique which enables very fast point to point shortest path distance computations and are based on a precomputed point to point distance table of a small subsets of nodes - the transit nodes. For the first time we construct instance based lower bounds on the size of transit node sets by interpreting a LP formulation of the problem and its dual and, as a side product, we achieve considerably smaller access node sets which directly improve the query time for non-local queries. We devise an algorithm to construct transit node sets for this theoretic framework and verify their properties with a practical implementation. This result was also published as ''Transit Nodes - Lower Bounds and Refined Construction'' at the 14th Meeting on Algorithm Engineering and Experiments (ALENEX) in 2012. - Applications of speedup Techniques: Path Prediction In the second chapter of this work we work on the path prediction problem - given the path a mobile user has moved along in a road network up to the current moment, predict where the user will move along in the near future. In contrast to known solutions to this problem we will compute our prediction not only based on the geometry of the known path (using extrapolation) or directional information implied by the underlying road network but make explicit use of the structure of the space of shortest paths in the network. Our proposed path prediction algorithm is equally simple but yields extremely accurate predictions at a very low computational cost. This work was published as path of the paper ''Algorithms for Matching and Predicting Trajectories'' in the 13th Meeting on Algorithm Engineering and Experiments (ALENEX) at 2011. - Applications of speedup Techniques: Sequenced Route Queries The third and final chapter considers the problem of a sequenced route query - the problem of planning an optimal route (quickest or shortest) that visits facilities of the respective type (for example a gas station or a super market) on the way home. The proposed solution, based on the combination of a distance sensitive doubling technique and contraction hierarchies, is orders of magnitudes faster than either a naive approach or previous results. In addition it produces the answers in an instant for realistic queries without compromising guaranteed optimality. With such fast query times, this type of route query becomes feasible even on mobile devices or for high-throughput web-based route planners. This work is published as ''Sequenced Route Queries: Getting Things Done on the Way Back Home'' in the Proceedings of the 20th International Conference on Advances in Geographic Information Systems (SIGSPATIAL) in 2012.