Person: Storandt, Sabine
Email Address
ORCID
Birth Date
Job Title
Last Name
First Name
Name
Search Results
Mind the Gap : Edge Facility Location Problems in Theory and Practice
Motivated by applications in urban planning, network analysis, and data visualization, we introduce center selection problems in graphs where the centers are represented by edges. This is in contrast to classic center selection problems where centers are usually placed at the nodes of a graph. Given a weighted graph G(V, E) and a budget k∈N, the goal is to select k edges from E such that the maximum distance from any point of interest in the graph to its nearest center is minimized. We consider three different problem variants, based on defining the points of interest either as the edges of G, or the nodes, or all points on the edges. We provide a variety of hardness results and approximation algorithms. A key difficulty of edge center selection is that the underlying distance function may not satisfy the triangle inequality, which is crucially used in approximation algorithms for node center selection. In addition, we introduce efficient heuristics that produce solutions of good quality even in large graphs, as demonstrated in our experimental evaluation.
Algorithms for Landmark Hub Labeling
Landmark-based routing and Hub Labeling (HL) are shortest path planning techniques, both of which rely on storing shortest path distances between selected pairs of nodes in a preprocessing phase to accelerate query answering. In Landmark-based routing, stored distances to landmark nodes are used to obtain distance lower bounds that guide A* search from node s to node t. With HL, tight upper bounds for shortest path distances between any s-t-pair can be interfered from their stored node labels, making HL an efficient distance oracle. However, for shortest path retrieval, the oracle has to be called once per edge in said path. Furthermore, HL often suffers from a large space consumption as many node pair distances have to be stored in the labels to allow for correct query answering. In this paper, we propose a novel technique, called Landmark Hub Labeling (LHL), which integrates the landmark concept into HL. We prove better worst-case path retrieval times for LHL in case it is path-consistent (a new labeling property we introduce). Moreover, we design efficient (approximation) algorithms that produce path-consistent LHL with small label size and provide parametrized upper bounds, depending on the highway dimension h or the geodesic transversal number gt of the graph. Finally, we show that the space consumption of LHL is smaller than that of (hierarchical) HL, both in theory and in experiments on real-world road networks.
Gradual road network simplification with shape and topology preservation
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.
Group Diagrams for simplified representation of scanpaths
We instrument Group Diagrams (GDs) to reduce clutter in sets of eye-tracking scanpaths. Group Diagrams consist of trajectory subsets that cover, or represent, the whole set of trajectories with respect to some distance measure and an adjustable distance threshold. The original GDs allow for an application of various distance measures. We implement the GD framework and evaluate it on scanpaths that were collected by a former user study on public transit maps. We find that the Fréchet distance is the most appropriate measure to get meaningful results, yet it is flexible enough to cover outliers. We discuss several implementation-specific challenges and improve the scalability of the algorithm. To evaluate our results, we conducted a qualitative study with a group of eye-tracking experts. Finally, we note that our enhancements are also beneficial within the original problem setting, suggesting that our approach might be applicable to various types of input data.
Robust visualization of trajectory data
The analysis of movement trajectories plays a central role in many application areas, such as traffic management, sports analysis, and collective behavior research, where large and complex trajectory data sets are routinely collected these days. While automated analysis methods are available to extract characteristics of trajectories such as statistics on the geometry, movement patterns, and locations that might be associated with important events, human inspection is still required to interpret the results, derive parameters for the analysis, compare trajectories and patterns, and to further interpret the impact factors that influence trajectory shapes and their underlying movement processes. Every step in the acquisition and analysis pipeline might introduce artifacts or alterate trajectory features, which might bias the human interpretation or confound the automated analysis. Thus, visualization methods as well as the visualizations themselves need to take into account the corresponding factors in order to allow sound interpretation without adding or removing important trajectory features or putting a large strain on the analyst. In this paper, we provide an overview of the challenges arising in robust trajectory visualization tasks. We then discuss several methods that contribute to improved visualizations. In particular, we present practical algorithms for simplifying trajectory sets that take semantic and uncertainty information directly into account. Furthermore, we describe a complementary approach that allows to visualize the uncertainty along with the trajectories.
Customizable Hub Labeling : Properties and Algorithms
Hub Labeling (HL) is a state-of-the-art preprocessing-based technique for route planning in road networks. It is a special incarnation of distance labeling, and it is well-studied in both theory and practice. The core concept of HL is to associate a label with each vertex, which consists of a subset of all vertices and respective shortest path information, such that the shortest path distance between any two vertices can be derived from considering the intersection of their labels. HL provides excellent query times but requires a time-consuming preprocessing phase. Therefore, in case of edge cost changes, rerunning the whole preprocessing is not viable. Inspired by the concept of Customizable Route Planning, we hence propose in this paper a Customizable Hub Labeling variant for which the edge costs in the network do not need to be known at construction time. These labels can then be used with any edge costs after conducting a so called customization phase. We study the theoretical properties of Customizable Hub Labelings, provide an O(log2n)-approximation algorithm for the average label size, and propose efficient customization algorithms.
Bounds and Algorithms for Geodetic Hulls
The paper is devoted to the study of geodetic convex hulls in graphs from a theoretical and practical perspective. The notion of convexity can be transferred from continuous geometry to discrete graph structures by defining a node subset to be (geodetically) convex if all shortest paths between its members do not leave the subset. The geodetic convex hull of a node set W is the smallest convex superset of W. The hull number of a graph is then defined as the size of the smallest node subset S (called hull set) whose convex hull contains all graph nodes. In contrast to the geometric setting, where the point subset on the boundary of the convex hull can be computed in polynomial time, it is NP-hard to decide whether a graph has a hull set of size at most s∈N. We establish novel theoretical bounds for graph parameters related to convex graph structures, and also design practical algorithms for upper and lower bounding the hull number. We evaluate the quality of our bounds as well as the performance of the proposed algorithms on road networks and wireless sensor networks of varying size.
On the generalized fréchet distance and its applications
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.
Sublinear Search Spaces for Shortest Path Planning in Grid and Road Networks
Shortest 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.