About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
Algorithms for Searching Massive Graphs
Abstract
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 problems in deductive database systems. In this paper, we present a novel data structuring technique and show how a branch and bound search algorithm can use this data structuring to prune the search space. Simulation results confirm that, using these techniques, a search can be expedited significantly without incurring a large storage penalty. As a side benefit, it is possible to organize the search to.obtain successive approximations to the desired solution with considerable reduction in total search. © 1994 IEEE