Efficient algorithms for navigation on large transportation graphs

We study the problem of serving shortest path (s.p.) information for large-scale transportation graphs (hundreds of thousands to millions of nodes) in the context of intelligent transportation systems (ITSs) and geographic information systems (GISs). In such systems, a database must serve queries of a specific sort-either path-based (“What is the shortest path from s to t?”) or direction-based (“What are the next arcs along this path?”)—with low latency and high throughput.; Previous approaches to this problem have generally utilized massive preprocessing to tabulate a substantial portion of the solution to the all-pairs s.p. problem. Their applicability to large-scale real transportation graphs (>100,000 nodes) is limited by the storage required for preprocessed data, and/or the time required for these initial computations. In addition, they are generally unable to deal with dynamically changing traffic conditions for graphs of this size (i.e., they are static). Proposed heuristic solutions either do not guarantee optimality, or are outperformed by these other methods.; We first design a static algorithm that utilizes a hierarchical data structure that can efficiently answer both directional and complete path queries. To achieve this goal, we also present a general purpose partitioning technique for transportation graphs with provable complexity bounds that are optimized for the construction of the hierarchical data structures for such navigation systems. We tested this algorithm on subgraphs of the transportation system of central Los Angeles. The results show that it either outperforms the previous well-known algorithms or has competitive performance while offering improved scalability with respect to space requirements.; Our second algorithm is radically different from the large-scale algorithms previously proposed and is designed to adapt to changing traffic patterns. Its storage requirements and preprocessing time are both significantly lower than these other techniques-requiring seconds, for example, rather than hours on the transportation graph of Los Angeles. Yet our solution is competitive in performance on queries. We describe an implementation of this algorithm with experimental results based on the transportation graph of L.A. County.