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.

REFERENCES

• 1: Philip Bohannon , Wenfei Fan , Michael Flaster , P. P. S. Narayan, Information preserving XML schema embedding, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 2: Christian Borgelt , Michael R. Berthold, Mining Molecular Fragments: Finding Relevant Substructures of Molecules, Proceedings of the 2002 IEEE International Conference on Data Mining, p.51, December 09-12, 2002
• 3: H. Bunke. Graph Matching: Theoretical Foundations, Algorithms, and Applications. in Vision Interface, pages 82--88, 2000.
• 4: Chen Chen , Xifeng Yan , Philip S. Yu , Jiawei Han , Dong-Qing Zhang , Xiaohui Gu, Towards graph containment search and indexing, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 5: James Cheng , Yiping Ke , Wilfred Ng , An Lu, Fg-index: towards verification-free query processing on graph databases, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247574]
• 6: D. Conte, P. Foggia, C. Sansone, and M. Vento. Thirty Years Of Graph Matching In Pattern Recognition. IJPRAI, 18, 3 (2004), 265--298.
• 7: Luigi P. Cordella , Pasquale Foggia , Carlo Sansone , Mario Vento, A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.10, p.1367-1372, October 2004 [doi>10.1109/TPAMI.2004.75]
• 8: S. Fortin, The Graph Isomorphism Problem, in Univ. of Alberta. 1996.
• 9: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 10: Ashish Kumar Gupta , Dan Suciu, Stream processing of XPath queries with predicates, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872809]
• 11: Huahai He , Ambuj K. Singh, Closure-Tree: An Index Structure for Graph Queries, Proceedings of the 22nd International Conference on Data Engineering, p.38, April 03-07, 2006 [doi>10.1109/ICDE.2006.37]
• 12: H. Jiang, H. Wang, P. S. Yu, and S. Zhou. GString: A Novel Approach for Efficient Search in Graph Databases. in ICDE, 2007.
• 13: Michihiro Kuramochi , George Karypis, Frequent Subgraph Discovery, Proceedings of the 2001 IEEE International Conference on Data Mining, p.313-320, November 29-December 02, 2001
• 14: Y. Liu, J. Li, and H. Gao. Summarizing Graph Patterns. in ICDE, 2008.
• 15: B. T. Messmer and H. Bunke. A decision tree approach to graph and subgraph isomorphism detection. Pattern Recognition, 32, 12 (1999), 1979--1998.
• 16: Bruno T. Messmer , Horst Bunke, Efficient Subgraph Isomorphism Detection: A Decomposition Approach, IEEE Transactions on Knowledge and Data Engineering, v.12 n.2, p.307-323, March 2000 [doi>10.1109/69.842269]
• 17: Haichuan Shang , Ying Zhang , Xuemin Lin , Jeffrey Xu Yu, Taming verification hardness: an efficient algorithm for testing subgraph isomorphism, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453899]
• 18: Dennis Shasha , Jason T. L. Wang , Rosalba Giugno, Algorithmics and applications of tree and graph searching, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543620]
• 19: J. R. Ullmann, An Algorithm for Subgraph Isomorphism, Journal of the ACM (JACM), v.23 n.1, p.31-42, Jan. 1976 [doi>10.1145/321921.321925]
• 20: Takashi Washio , Hiroshi Motoda, State of the art of graph-based data mining, ACM SIGKDD Explorations Newsletter, v.5 n.1, July 2003 [doi>10.1145/959242.959249]
• 21: D. W. Williams, J. Huan, and W. Wang. Graph Database Indexing Using Structured Graph Decomposition. in ICDE, 2007.
• 22: M. Worlein, Extension and parallelization of a graphmining-algorithm, in Friedrich-Alexander-Universität. 2006.
• 23: Xifeng Yan , Jiawei Han, gSpan: Graph-Based Substructure Pattern Mining, Proceedings of the 2002 IEEE International Conference on Data Mining, p.721, December 09-12, 2002
• 24: Xifeng Yan , Jiawei Han, CloseGraph: mining closed frequent graph patterns, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956784]
• 25: Xifeng Yan , Philip S. Yu , Jiawei Han, Graph indexing: a frequent structure-based approach, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007607]
• 26: S. Zhang, M. Hu, and J. Yang. TreePi: A Novel Graph Indexing Method. in ICDE, 2007.
• 27: Peixiang Zhao , Jeffrey Xu Yu , Philip S. Yu, Graph indexing: tree + delta <= graph, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 28: Lei Zou , Lei Chen , Jeffrey Xu Yu , Yansheng Lu, A novel spectral coding in a large graph database, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France [doi>10.1145/1353343.1353369]