ALGORITHMS FOR SEARCHING MASSIVE GRAPHS

Given a large graph, stored on disk, there is often a need to perform a search over this graph. Such a need could arise, for example, in the search component of a data-intensive expert system or to solve path p roblems in deductive database systems. In this paper, we present a nov el data structuring technique and show how a branch and bound search a lgorithm can use this data structuring to prune the search space. Simu lation results confirm that, using these techniques, a search can be e xpedited significantly without incurring a large storage penalty. As a side benefit, it is possible to organize the search to obtain success ive approximations to the desired solution with considerable reduction in total search.