External Data Structures for Shortest Path Queries on Planar Digraphs

摘要

In this paper we present space-query trade-offs for external memory data structures that answer shortest path queries on planar directed graphs. For any S = Ω(N~(1+∈)) and S = O(N~2/B), our main result is a family of structures that use S space and answer queries in O((N~2)/(SB)) I/Os, thus obtaining optimal space-query product O(N~2/B). An S space structure can be constructed in O(S~(1/2) · sort(N)) I/Os, where sort(N) is the number of I/Os needed to sort N elements, B is the disk block size, and N is the size of the graph.