In this paper, we consider the problem of gradual road network simplification, where given an embedded road network the goal is to compute a fine-grained succession of simplifications with decreasing level-of-detail. This allows to render the network on any desired zoom level or with a user-defined number of segments. Previous work has established that this can be achieved based on a Contraction Hierarchies (CH) data structure. CH was originally developed as a graph preprocessing method to speed up shortest path planning in road networks. However, since it is inherently based on a graph simplification mechanism, it can also serve as a basis for rendering. But the existing method exhibits several shortcomings, for example, topological inconsistencies arise on many simplification levels and the preservation of the shape of routes and the overall network for coarser graph representations is insufficient. This severely impairs the navigability of the map. We significantly improve upon the existing method by modifying the CH construction process as well as the rendering algorithm.

Measuring the similarity of spatio-temporal trajectories in a sensible fashion is an important building block for applications such as trajectory clustering or movement pattern analysis. However, typically employed similarity measures only take the spatial components of the trajectory into account, or are complicated combinations of different measures. In this paper we introduce the so called Generalized Fréchet distance, which extends the well-known Fréchet distance. For two polygonal curves of length n and m in d-dimensional space, the Generalized Fréchet distance enables an individual weighting of each dimension on the similarity value by using a convex function. This allows to integrate arbitrary data dimensions as e.g. temporal information in an elegant, flexible and application-aware manner. We study the Generalized Fréchet Distance for both the discrete and the continuous version of the problem, prove useful properties, and present efficient algorithms to compute the decision and optimization problem. In particular, we prove that for d ∈ O(1) the asymptotic running times of the optimization problem for the continuous version are O(nm log(nm)) under realistic assumptions, and O(nm) for the discrete version for arbitrary weight functions. Therefore the theoretical running times match those of the classical Fréchet distance. In our experimental evaluation, we demonstrate the usefulness of the Generalized Fréchet distance and study the practical behaviour of our algorithms. On sets of real-world trajectories, we confirm that the weighting of the spatial and temporal dimensions heavily impacts the relative similarity, and hence the ability to tailor the measure to the application is a useful tool.

We present a holistic approach for pedestrian routing that allows computing shortest paths that may have indoor and outdoor sections. Such routes arise, for example, when the destination is not just an address but a specific store in a large mall, or when one needs to get to a certain track at a large train station. Currently, map services as Google Maps or OSRM do not offer such functionality. We identify and overcome three main challenges for answering such complex route planning queries: (i) Pedestrian routing requires fine-grained data, as the location of stairs and elevators, building dventrances, building footprints, and elevation/level information. A single missing staircase can change the length of the computed path severely. (ii) Indoor routing has to be integrated carefully into classical path planning to allow the computation of sensible routes that may enter and exit buildings. (iii) Given the large amount of data to be considered in a query, acceleration techniques need to be applied in order to achieve interactive query times. Retrieving barrier-free routes for wheelchairs is also our important use case.

We present new generic methods to efficiently draw schematized metro maps for a wide variety of layouts, including octilinear, hexalinear, and orthoradial maps. The maps are drawn by mapping the input graph to a suitable grid graph. Previous work was restricted to regular octilinear grids. In this work, we investigate a variety of grids, including triangular grids and orthoradial grids. In particular, we also construct sparse grids where the local node density adapts to the input graph (e.g. octilinear Hanan grids, which we introduce in this work). For octilinear maps, this reduces the grid size by a factor of up to 5 compared to previous work, while still achieving close-to-optimal layouts. For many maps, this reduction also leads to up to 5 times faster solution times of the underlying optimization problem. We evaluate our approach on five maps. All octilinear maps can be computed in under 0.5 seconds, all hexalinear and orthoradial maps can be computed in under 2.5 seconds.

We consider the problem of indexing massive trajectory data in an underlying road network. Our Pathfinder index structure is based on a state-of-the-art speed-up technique for shortest path planning and allows to both compress and access huge amounts of trajectory data. In a continent-sized network with more than 400 million nodes and almost a billion edges, Pathfinder allows to retrieve all trajectories within a given space-time cube in a few microseconds per reported trajectory. The applicability of Pathfinder is shown using both synthetic and real-world trajectory sets.

We present CYCLOPS, a route planning system for cyclists that allows for intuitive specification of preferences for a route query, and also suggests several alternative route options. It combines three metrics of the underlying road network relevant to cyclists (distance, positive height gain, unsuitability for cycling), to cater for different cycling habits. The CYCLOPS back end is based on state-of-the-art multi-criteria route planning techniques, the front end is realized using the HTML5 Canvas API to provide an intuitive interface for combining metrics in personalized route planning queries and a visualization of the routes found.

We present LOOM (Line-Ordering Optimized Maps), an automatic generator of geographically accurate transit maps. The input to LOOM is data about the lines of a transit network: for each line, its station sequence and geographical course. LOOM proceeds in three stages: (1) construct a line graph, where edges correspond to network segments with the same set of lines following the same course; (2) apply a set of local transformation rules that compute an optimal partial ordering of the lines and speed up the next stage; (3) construct an Integer Linear Program (ILP) that yields a line ordering for each edge and minimizes the total number of line crossings and line separations; and (4) based on the line graph and the computed line ordering, draw the map. As our maps respect the geography of the transit network, they can be used as overlays in typical map services. Previous research either did not take the network geography into account or was only concerned with schematic metro map layouting. We evaluate LOOM on six real-world transit networks, with line-ordering search-space sizes up to 2 × 10 267 . Using our transformation rules and an improved ILP formulation, we compute optimal line orderings in a fraction of a second for all networks. This enables interactive use of our method in map editors.

Real-world route planning problems are conventionally modeled as weighted graphs - either as grid graphs for open spaces or as path/road networks. The edge weights (e.g. Euclidean distances, travel times or energy consumption) are then derived from measurements or estimations. But the resulting weights are often overly precise and demand a lot of space to be stored. In addition, operations on these weights are computationally expensive. The common approach to avoid those problems is to round edge weights to reasonable precisions (e.g. whole meters, seconds or watt). Unfortunately, naive rounding schemes can easily distort the structure of optimal paths in the graph. In this paper, we present a novel rounding framework based on the construction of an overlay graph. We show that a carefully designed overlay graph based on so called contraction hierarchies can accelerate shortest path computations and minimize rounding errors at the same time, while demanding little space on its own.

We consider the problem of indexing the complete OpenStreetMap planet data set (> 500GB of raw data) to support complex queries involving both text search as well as context-aware spatial relations. This requires (a) formalization of spatial relations like 'north of', 'between', 'near' depending on the context, and (b) the development of suitable data representations to integrate textual and spatial information for efficient query performance.

We consider the problem of generating concise and robust driving directions that avoid overly detailed turn-by-turn instructions as long as one is not too close to the final destination. Our approach is based on a deliberate selection of cities as landmarks that are likely to appear on road signs along the route. For a route from Stuttgart to Flensburg, the route description could read "Go towards Frankfurt, then Kassel, then Hanover, then Hamburg". Apart from being more compact, such driving directions are also more robust against wrong turns taken. While an implementation based on Dijkstra's algorithm takes on the order of several seconds to generate such driving directions, a careful instrumentation of speed-up techniques reduces this to fractions of a second required, e.g., for a web service.

We study the problem of learning individual route preferences of drivers. Most current route planning services only compute shortest or quickest paths. But many other criteria might play a role for a user to prefer a certain route, as, e.g., fuel consumption, jam likeliness, road conditions, scenicness of the route, turns, allowed maximum speeds, toll costs and many more. Specifying the importance of each criterion manually is a non-trivial, unintuitive and time consuming undertaking for a user. Therefore, we develop approaches that deduce such preferences automatically based on paths previously driven by the user. We present an LP-formulation of the problem making use of a Dijkstra-based separation oracle. The resulting algorithm runs in polynomial time and allows for the user preference computation in few seconds even if several hundred routes are taken into account. Our experiments show that new route suggestions based on these learned preferences reflect the users definition of an optimal route very well.

We show how to estimate population numbers for arbitrary user-defined regions, down to the level of individual buildings. This is important for various applications like evacuation planning, facility placement, or traffic estimation. However, census data with precise population numbers is typically only available at the level of cities, villages, or districts, if at all.

Computing shortest paths in road networks with millions of nodes and edges is challenging on its own. In the last few years, several preprocessing-based acceleration techniques have been developed to enable query answering orders of magnitudes faster than a plain Dijkstra computation. But most of these techniques work only if the metric which determines the optimal path is static or rarely changes. In contrast to that, we aim at answering personalized route planning queries. Here, every single query comes with a specification of its very own metric. This increases the combinatorial complexity of the problem significantly. We develop new preprocessing schemes that allow for real-time personalized route planning in huge road networks while keeping the memory footprint of the preprocessed data and subsequent queries small.

We introduce a framework to create a world-wide live map of public transit, i.e. the real-time movement of all buses, subways, trains and ferries. Our system is based on freely available General Transit Feed Specification (GTFS) timetable data and also features real-time delay information (where available). The main problem of such a live tracker is the enormous amount of data that has to be handled (millions of vehicle movements). We present a highly efficient back-end that accepts temporal and spatial boundaries and returns all relevant trajectories and vehicles in a format that allows for easy rendering by the client. The real-time movement visualization of complete transit networks allows to observe the current state of the system, to estimate the transit coverage of certain areas, to display delays in a neat manner, and to inform a mobile user about near-by vehicles. Our system can be accessed via http://tracker.geops.ch/. The current implementation features over 80 transit networks, including the complete Netherlands (with real-time delay data), and various metropolitan areas in the US, Europe, Australia and New Zealand. We continuously integrate new data. Especially for Europe and North America we expect to achieve almost full coverage soon.

We present TRAVIC, a thin browser-based client that is able to display smooth vehicle movements on a map. The focus is on visualizing world-wide public transit vehicle movements in an interactive way. But we also investigate other use cases, for example, traffic simulation. We describe in detail which server requests are fired and how the received data is handled. We also provide a performance evaluation conducted on several browsers. We show that, in combination with an efficient back-end, TRAVIC is able to display many thousands of vehicle movements in real-time. Our prototype implementation can be accessed under http://tracker.geops.ch.

We consider the application of route planning in large public-transportation networks (buses, trains, subways, etc). Many connections in such networks are operated at periodic time intervals. When a set of connections has sufficient periodicity, it becomes more efficient to store the time range and frequency (e.g., every 15 minutes from 8:00am-6:00pm) instead of storing each of the time events separately. Identifying an optimal frequency-compression is NP-hard, so we present a time- and space-efficient heuristic.

For a directed graph G with vertex set V we call a subset C ⊆ V a k-(All-)Path Cover if C contains a node from any path consisting of k nodes. This paper considers the problem of constructing small k -Path Covers in the context of road networks with millions of nodes and edges. In many application scenarios the set C and its induced overlay graph constitute a very compact synopsis of G which is the basis for the currently fastest data structure for personalized shortest path queries, visually pleasing overlays of subsampled paths, and efficient reporting, retrieval and aggregation of associated data in spatial network databases. Apart from a theoretical investigation of the problem, we provide efficient algorithms that produce very small k -Path Covers for large real-world road networks (with a posteriori guarantees via instance-based lower bounds).

We propose a novel scheme for map matching and fully autonomous self-localization. Our scheme is based on the unique characteristics of the shape of paths in a road network. As uniqueness of path shapes comes as no surprise in a world of infinite precision, we develop robust means of comparing shapes of paths under imprecisions. Even under this fuzzy comparison model, path shapes turn out to be sufficiently characteristic to allow for map matching or fully autonomous self-localization. We design an efficient data structure which allows for very fast path shape queries.