The Taub Faculty of Computer Science Events and Talks

In recent years, the practical need for fast retrieval of shortest path queries has significantly increased, in part due to the developing GPS navigation systems and other route planning softwares.

Classical shortest paths algorithms such as Dijkstra's algorithm return shortest path distance in almost linear time in the number of nodes. However, continent-sized road networks require something much faster. It is possible to achieve sublinear-time queries if preprocessing is allowed. A distance oracle is a data structure that allows fast retrieval of a distance estimate for any pair of nodes. The focus in designing distance oracles is often on the tradeoff between several parameters: the construction time (the time it takes to construct the distance oracle), the size of the data structure, the query time and the quality of the answer (how close is the estimated distance to the real distance).

Not only are distance oracles important structures by their own right with both practical and theoretical interest, but they also have strong-ties to numerous other problems in theory and distributed computing, such as spanners, compact routing schemes and low-stretch spanning trees. A major complicating aspect is that real-world networks may change over time. The changes may be either permanent (e.g., some road is added to the network) or temporary (e.g., some roads may be closed for short periods or a major junction may be temporary blocked).

A dynamic setting is used to capture permanent changes to the network, whereas a fault tolerance setting captures temporary changes.

In the first part of the talk I will highlight some of my work on shortest path queries in static, dynamic and fault-tolerant settings. In the second part of the talk I will discuss my recent work on constant time distance oracles, which essentially obtains optimal bounds for general graphs and improves over the Thorup-Zwick distance oracle [STOC ’01, J.ACM ‘05].

Bio:
Shiri is a postdoctoral researcher at Microsoft Research Silicon Valley. She completed her Ph.D. under the supervision of Prof. David Peleg at the Weizmann Institute of Science. Her main research interests are in the design and analysis of combinatorial algorithms, with a special focus on algorithms at the interface of distributed computing, networking and data structures. She has published papers on a variety of algorithmic topics including graph spanners, distance oracles/labeling, compact routing, dynamic algorithms, approximation algorithms, and social networks.