ANALYSIS AND EXPERIMENTAL EVALUATION OF TIME-DEPENDENT DISTANCE ORACLES

Urban road networks are typically represented as directed graphs equipped with some metric which assigns distance functions (rather than scalars) to the arcs, e.g., representing the traversal times as functions of the departure time from their tails. Such a metric is usually created by sampling the distance values of all the arcs at certain points in time, and then considering the interpolants of these sampled values as the corresponding (periodic, continuous, piecewise linear) distance functions of the arcs. Distance oracles and speedup techniques aim to create appropriate traffic metadata (distance summaries, or search profiles) during a preprocessing phase, in order to be able to respond to shortest-path queries significantly faster than a typical Dijkstra run. Distance oracles focus mainly on provable worst/average case guarantees on preprocessing time/space complexities, query time complexity and approximation ratio. Speedup techniques emphasize on the thorough experimental evaluation of their performance on real large-scale road network instances.In this work, we experimentally evaluate the only time-dependent distance oracles existing so far on a truly real-world time-dependent data set (city of Berlin). In particular: (i) We present a new time-dependent distance oracle whose preprocessing phase is based on a new approximation technique for creating approximate distance summaries, that is a quite simple and fast one-to-all approximation method. (ii) We conduct an extensive experimental study with three query algorithms and six different landmark sets, achieving remarkable speedups over the time-dependent variant of Dijkstra'a algorithm.We describe here all the implementation details concerning the digestion of the raw traffic data, along with several heuristic improvements of both the preprocessing phase and the query algorithms, which are crucial for their experimental analysis. Our results are quite encouraging, achieving speedups by two orders of magnitude versus a typical time-dependent Dijkstra run, while in the vast majority of the queries the exact solution is discovered.