Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks

Given two vertices of interest (POIs) s and t on a spatial network, a distance (path) query returns the shortest network distance (shortest path) from s to t. This query has a variety of applications in practice and is a fundamental operation for many database and data mining algorithms.

In this paper, we propose an efficient distance and path oracle on dynamic road networks using the randomization technique. Our oracle has a good performance in practice and remarkably, and at the same time, it has a favorable theoretical bound. Specifically, it has O(n log 2 n) (resp. O(n log 2 n)) preprocessing time (resp. space) and O(log 4 n log log n) (resp. O(log 4 n log log n + l)) distance query time (resp. shortest path query time) as well as O(log 3 n) update time with high probability (w.h.p.), where n is the number of vertices in the spatial network and l is the number of edges on the shortest path. Our experiments show that the existing oracles suffer from a huge updating time that renders them impractical and our oracle enjoys a negligible updating time and meanwhile has comparable query time and indexing cost with the best existing oracle.