Algorithms for Searching Massive Graphs

Rakesh Agrawal, H. V. JagadishIEEE TKDE 1994 · OpenReview

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 the total search.<
BibTeX
@article{agrawal1994algorithms,
  author = {Rakesh Agrawal and H. V. Jagadish},
  title = {{Algorithms for Searching Massive Graphs}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {1994},
  url = {https://openreview.net/forum?id=L8hms8c3Wo},
}

Loading related content...

Figure