Blocking for External Graph Searching

M. H. Nodine, M. T. Goodrich, and J. S. Vitter. ``Blocking for External Graph Searching,'' Algorithmica, 16(2), August 1996, 181-214. A shortened version appears in Proceedings of the 12th Annual ACM Symposium on Principles of Database Systems (PODS '93), Washington, D. C, May 1993.

Full text (Adobe pdf format)

In this paper, we consider the problem of using disk blocks efficiently in searching graphs that are too large to fit in internal memory. Our model allows a vertex to be represented any number of times on the disk in order to take advantage of redundancy. We give matching upper and lower bounds for complete $d\/$-ary trees and $d\/$-dimensional grid graphs, as well as for classes of general graphs that intuitively speaking have a close to uniform number of neighbors around each vertex.