External Memory Algorithms for Shortest Distance Queries

Efficient computation of shortest distances over large static graphs is
vital in several applications including web modeling, large communication
systems, network analysis, intelligent transportation system and advanced
spatio-temporal databases.

A natural strategy is to preprocess the graph so that distance can be
answered efficiently. Such a scheme should have following properties: (a)
the data structure from preprocessing should be small (b) CPU and Disk I/O
cost for per shortest distance computation be low and (c) it should
provide worst case performance guarantees for both storage and distance
computation cost. Current techniques lack one or more of these properties.

We present two algorithms to bridge this gap for graphs that can be
partitioned efficiently. We present the asymptotic complexity of our
algorithm over planar graphs. The first of our algorithms finds shortest
distance using O(n \sqrt n) space in O(log n) time and O(1) disk accesses.

Our second algorithm reduces storage cost at the expense of distance
computation performance. Our data structure requires O(n \sqrt \sqrt n)
space while the distance computation requires O(\sqrt \sqrt n log n) time.
Our experiments with real-world and synthetic datasets show that our
algorithms are efficient and represent a tunable mechanism for making
tradeoffs between CPU costs and storage requirements.