BLOCKING FOR EXTERNAL GRAPH SEARCHING

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 di sk in order to take advantage of redundancy. We give matching upper an d lower bounds for complete d-ary trees and d-dimensional grid graphs, as well as for classes of general graphs that intuitively speaking ha ve a close to uniform number of neighbors around each vertex. We also show that, for the special case, of grid graphs blocked with isothetic hypercubes,there is a provably better speed-up if even a small amount of redundancy is permitted.