Haichuan Shang
Jeffrey Xu Yu
Abstract
Graphs are widely used to model complicated data semantics in many applications. In this paper, we aim to develop efficient techniques to retrieve graphs, containing a given query graph, from a large set of graphs. Considering the problem of testing subgraph isomorphism is generally NP-hard, most of the existing techniques are based on the framework of filtering-and-verification to reduce the precise computation costs; consequently various novel feature-based indexes have been developed. While the existing techniques work well for small query graphs, the verification phase becomes a bottleneck when the query graph size increases. Motivated by this, in the paper we firstly propose a novel and efficient algorithm for testing subgraph isomorphism, QuickSI. Secondly, we develop a new feature-based index technique to accommodate QuickSI in the filtering phase. Our extensive experiments on real and synthetic data demonstrate the efficiency and scalability of the proposed techniques, which significantly improve the existing techniques.
- A. V. Aho, J. E. Hopcroft, and J. Ullman. Data Structures and Algorithms. 1983. Google Scholar
Digital Library
- V. Arvind and J. Köbler. Graph isomorphism is low for zpp(np) and other lowness results. In STACS, pages 431--442, 2000. Google ScholarDigital Library
- S. Berretti, A. D. Bimbo, and E. Vicario. Efficient matching and indexing of graph models in content-based retrieval. IEEE Trans. Pattern Anal. Mach. Intell., 23 (10):1089--1105, 2001. Google ScholarDigital Library
- J. Cheng, Y. Ke, W. Ng, and A. Lu. Fg-index: towards verification-free query processing on graph databases. In Proceedings of the ACM SIGMOD international conference on Management of data, pages 857--872, 2007. Google ScholarDigital Library
- Y. Chi, Y. Yang, and R. R. Muntz. Canonical forms for labelled trees and their applications in frequent subtree mining. Knowl. Inf. Syst., 8(2):203--234, 2005.Google ScholarCross Ref
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. 2001. Google ScholarDigital Library
- M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. New York, NY, USA, 1990. Google ScholarDigital Library
- R. Giugno and D. Shasha. Graphgrep: A fast and universal method for querying graphs. Proceedings of the International Conference on Pattern Recognition, 2:112--115 vol.2, 2002.Google ScholarCross Ref
- H. He and A. K. Singh. Closure-tree: An index structure for graph queries. In Proceedings of the International Conference on Data Engineering, page 38, 2006. Google ScholarDigital Library
- H. Jiang, H. Wang, P. S. Yu, and S. Zhou. Gstring: A novel approach for efficient search in graph databases. In Proceedings of the International Conference on Data Engineering, pages 566--575, 2007.Google ScholarCross Ref
- A. H. Land and A. G. Doig. An automatic method of solving discrete programming problems. Econometrica, 28(3):497--520.Google ScholarCross Ref
- B. T. Messmer and H. Bunke. A decision tree approach to graph and subgraph isomorphism detection. Pattern Recognition, 32(12):1979--1998, 1999.Google ScholarCross Ref
- J. R. Ullmann. An algorithm for subgraph isomorphism. J. ACM, 23(1):31--42, 1976. Google ScholarDigital Library
- D. W. Williams, J. Huan, and W. Wang. Graph database indexing using structured graph decomposition. In Proceedings of the International Conference on Data Engineering, pages 976--985, 2007.Google ScholarCross Ref
- X. Yan and J. Han. gspan: Graph-based substructure pattern mining. In Proceedings of the IEEE International Conference on Data Mining, page 721, 2002. Google ScholarDigital Library
- X. Yan, P. S. Yu, and J. Han. Graph indexing: a frequent structure-based approach. In Proceedings of the ACM SIGMOD international conference on Management of data, pages 335--346, 2004. Google ScholarDigital Library
- X. Yan, P. S. Yu, and J. Han. Substructure similarity search in graph databases. In Proceedings of the ACM SIGMOD international conference on Management of data, pages 766--777, 2005. Google ScholarDigital Library
- S. Zhang, M. Hu, and J. Yang. Treepi: A novel graph indexing method. In Proceedings of the International Conference on Data Engineering, pages 966--975, 2007.Google ScholarCross Ref
- P. Zhao and J. X. Yu. Fast frequent free tree mining in graph databases. World Wide Web, 11(1):71--92, 2008. Google ScholarDigital Library
- P. Zhao, J. X. Yu, and P. S. Yu. Graph indexing: tree + delta <= graph. In Proceedings of the International Conference on Very Large Data Bases, pages 938--949, 2007. Google ScholarDigital Library
- L. Zou, L. Chen, J. X. Yu, and Y. Lu. A novel spectral coding in a large graph database. In Proceedings of the International Conference on Extending Database Technology, 2008. Google ScholarDigital Library
Index Terms
- Taming verification hardness: an efficient algorithm for testing subgraph isomorphism
Recommendations
NP-hardness of multiple bondage in graphs
Let p 2 be a positive integer. The p -bondage number of a graph G is the minimum number of edges whose removal from G results in a graph with larger p -domination number. The p -total bondage number of a graph G with no isolated vertex is the minimum ...
Cosecure Domination: Hardness Results and Algorithms
Combinatorial AlgorithmsAbstractFor a simple graph without any isolated vertex, a cosecure dominating set S of G satisfies two properties, (i) S is a dominating set of G, (ii) for every vertex , there exists a vertex such that and is a ...
Hardness transitions and uniqueness of acyclic colouring
AbstractFor k ∈ N, a k-acyclic colouring of a graph G is a function f : V ( G ) → { 0 , 1 , … , k − 1 } such that (i) f ( u ) ≠ f ( v ) for every edge u v of G, and (ii) there is no cycle in G bicoloured by f. For k ∈ N, the problem k-Acyclic ...
Comments