ALGORITHMS FOR SEARCHING MASSIVE GRAPHS

被引：18

作者：

AGRAWAL, R ^{[1
]}

JAGADISH, HV ^{[1
]}

机构：

[1] AT&T BELL LABS,MURRAY HILL,NJ 07974

来源：

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING | 1994年 / 6卷 / 02期

关键词：

DEDUCTIVE DATABASE SYSTEMS; SEARCH TECHNIQUES; BRANCH AND BOUND; APPROXIMATION TECHNIQUES; PATH QUERIES; QUERY PROCESSING; SHORTEST DISTANCE IN A GRAPH;

D O I：

10.1109/69.277767

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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.

引用

页码：225 / 238

页数：14