Tech Report CS-92-44

Blocking for External Graph Searching

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

September 1992


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)