Research

Jump directly to the list of publications.

My research interests are algorithms, data structures, and graphs, in particular shortest-path algorithms. Most of my research results address the problem of efficiently computing a shortest path between two nodes of a network --— a problem with numerous applications. The shortest-path query problem in particular occurs in transportation (route planning and navigation or also logistics and traffic simulations), in packet routing, in social networks, and in many other scenarios. Furthermore, shortest-path problems occur as subproblems in various optimization problems (e.g., state-of-the-art network-flow algorithms for planar graphs internally compute numerous shortest paths).

Strategies for computing answers to shortest-path queries may involve the use of pre-computed data structures (often called distance oracles) in order to improve the query time. Designing a shortest-path-query processing method raises questions such as: How can these data structures be computed efficiently? What amount of storage is necessary? How much improvement of the query time is possible? How good is the approximation quality (also termed stretch) of the query result? And, in particular, what are the tradeoffs between pre-computation time, storage, query time, and approximation quality?

My research provides answers to these questions for static networks. I analyzed the tradeoff between storage and query time, both from a theoretical and from an experimental perspective. Let me briefly highlight some of my contributions (results obtained with co-authors, details on publication page); from theory to practice:

The tradeoffs of existing methods had been perceived as optimal, based on observations for networks with many edges (dense graphs). We shift attention to networks with few edges (sparse graphs), restarting investigations of better methods for more practical sparse networks. We prove that, even for sparse graphs, distance oracles with constant query time and stretch require «large» storage. We also prove that routing with additive distortion requires «large» routing tables.
If storage is scarce, for example on a mobile device, data structures may need to be particularly space-efficient. For planar graphs, we provide the data structure tradeoffs for essentially any storage restriction an application might have.
For road networks, there are methods that, according to experimental results, find routes in time proportional to the number of edges on the shortest path. We can formally explain this experimental behavior for planar graphs, providing a method with comparable worst-case performance guarantees. We also provide the theoretical justification for an algorithm very similar to the route planning method used in Microsoft's Bing Maps.
For complex networks, general data structures show much better experimental behavior than what the worst-case bounds would predict. We give the first rigorous explanation of this phenomenon, explaining the superior behavior of a popular heuristic.
For complex networks with a dense core and tree-like fringe, we provide a method using efficient data structures for graphs with small tree-width in the fringe, combined with approximation methods for the core. Our method preprocesses social networks with 70M links into a compact data structure of size 1GB and query time 0.06ms.
For general undirected graphs, we provide an easy-to-implement method based on Voronoi duals with extremely fast preprocessing times (less than one minute for 20M edges) and competitive, fast query times.

Please see the list of publications and the respective papers for details.