Tech Report CS-92-44

Blocking for External Graph Searching

Mark H. Nodine, Michael T. Goodrich, and Jeffrey Scott Vitter

September 1992

Abstract:

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.

(complete text in pdf or gzipped postscript)