Paper Info
Title
A novel approach for efficient supergraph query processing on graph databases
Abstract
In recent years, large amount of data modeled by graphs, namely graph data, have been collected in various domains. Efficiently processing queries on graph databases has attracted a lot of research attentions. Supergraph query is a kind of new and important queries in practice. A supergraph query, q, on a graph database D is to retrieve all graphs in D such that q is a supergraph of them. Because the number of graphs in databases is large and subgraph isomorphism testing is NP-complete, efficiently processing such queries is a big challenge. This paper first proposes an optimal compact method for organizing graph databases. 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 stored graphs to queries during query processing. Then, an exact algorithm and an approximate algorithm for generating significant feature set with optimal order are proposed to construct indices 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 of testing subgraph isomorphisms from multiple graphs to one graph is presented. Finally, based on all these techniques, a query processing method is proposed. Analytical and experimental results show that the proposed algorithms outper-form the existing similar algorithms by one to two orders of magnitude.
Year
DOI
Venue
2009
10.1145/1516360.1516385
EDBT
Keywords
Field
DocType
novel approach,efficient supergraph query processing,important query,optimal order,supergraph query,multiple graph,graph databases,graph database d,graph data,subgraph isomorphism testings,query processing,compact organization,business intelligence,data warehousing,data model,data integration
Data mining,Graph database,Exact algorithm,Computer science,Induced subgraph isomorphism problem,Theoretical computer science,Graph product,Factor-critical graph,Clique-width,Subgraph isomorphism problem,Graph (abstract data type),Database
Conference
Citations 
PageRank 
References 
32
0.89
24
Authors
4
Name
Order
Citations
PageRank
Shuo Zhang12119.44
Jianzhong Li23196304.46
Hong Gao31086120.07
Zhaonian Zou433115.78