Efficient algorithms for supergraph query processing on graph databases |
| |
Authors: | Shuo Zhang Xiaofeng Gao Weili Wu Jianzhong Li Hong Gao |
| |
Institution: | 1.Harbin Institute of Technology,Harbin,China;2.University of Texas at Dallas,Dallas,USA |
| |
Abstract: | We study the problem of processing supergraph queries on graph databases. A graph database D is a large set of graphs. A supergraph query
q on D is to retrieve all the graphs in D such that q is a supergraph of them. The large number of graphs in databases and the NP-completeness of subgraph isomorphism testing
make it challenging to efficiently processing supergraph queries. In this paper, a new approach to processing supergraph queries
is proposed. Specifically, a method for compactly organizing graph databases is first presented. Common subgraphs of the graphs
in a database are stored only once in the compact organization of the database, in order to reduce the overall cost of subgraph
isomorphism testings from the stored graphs to queries during query processing. Then, an exact algorithm and an approximate
algorithm for generating the significant feature set with optimal order are proposed, followed by the algorithms for indices
construction on graph databases. The optimal order on the feature set is to reduce the number of subgraph isomorphism testings
during query processing. Based on the compact organization of graph databases, a novel algorithm for testing subgraph isomorphisms
from multiple graphs to one graph is presented. Finally, based on all the above techniques, a query processing method is proposed.
Analytical and experimental results show that the proposed algorithms outperform the existing similar algorithms by one to
two orders of magnitude. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|