Xuguang Ren
Abstract
Subgraph Isomorphism is a fundamental problem in graph data processing. Most existing subgraph isomorphism algorithms are based on a backtracking framework which computes the solutions by incrementally matching all query vertices to candidate data vertices. However, we observe that extensive duplicate computation exists in these algorithms, and such duplicate computation can be avoided by exploiting relationships between data vertices. Motivated by this, we propose a novel approach, BoostIso, to reduce duplicate computation. Our extensive experiments with real datasets show that, after integrating our approach, most existing subgraph isomorphism algorithms can be speeded up significantly, especially for some graphs with intensive vertex relationships, where the improvement can be up to several orders of magnitude.
- A. V. Aho, M. R. Garey, and J. D. Ullman. The transitive reduction of a directed graph. SIAM, 1: 131--137, 1972.Google Scholar
Cross Ref
- Q. Chen, A. Lim, and K. W. Ong. D(k)-index: An adaptive structural summary for graph-structured data. In SIGMOD, pages 134--144, 2003. Google ScholarDigital Library
- L. P. Cordella, P. Foggia, C. Sansone, and M. Vento. A (sub) graph isomorphism algorithm for matching large graphs. Pattern Anal. Mach. Intell., IEEE Trans, 26(10): 1367--1372, 2004. Google ScholarDigital Library
- W. Fan, J. Li, X. Wang, and Y. Wu. Query preserving graph compression. In SIGMOD, pages 157--168, 2012. Google ScholarDigital Library
- M. R. Garey and D. S. Johnson. Computer and intractability. A Guide to the NP-Completeness, 1979. Google ScholarDigital Library
- W.-S. Han, J. Lee, and J.-H. Lee. Turbo iso: towards ultrafast and robust subgraph isomorphism search in large graph databases. In SIGMOD, pages 337--348, 2013. Google ScholarDigital Library
- H. He and A. K. Singh. Query language and access methods for graph databases. In Manag. and Min. Graph Data, pages 125--160. 2010.Google ScholarCross Ref
- R. Kaushik, P. Shenoy, P. Bohannon, and E. Gudes. Exploiting local similarity for indexing paths in graph-structured data. In ICDE, pages 129--140, 2002. Google ScholarDigital Library
- J. Lee, W.-S. Han, R. Kasperovics, and J.-H. Lee. An in-depth comparison of subgraph isomorphism algorithms in graph databases. In VLDB, pages 133--144, 2012. Google ScholarDigital Library
- T. Milo and D. Suciu. Index structures for path expressions. In ICDT, pages 277--295, 1999. Google ScholarDigital Library
- S. Navlakha, R. Rastogi, and N. Shrivastava. Graph summarization with bounded error. In SIGMOD, pages 419--432, 2008. Google ScholarDigital Library
- H. Shang, Y. Zhang, X. Lin, and J. X. Yu. Taming verification hardness: an efficient algorithm for testing subgraph isomorphism. PVLDB, 1(1): 364--375, 2008. Google ScholarDigital Library
- Z. Sun, H. Wang, H. Wang, B. Shao, and J. Li. Efficient subgraph matching on billion node graphs. PVLDB, 5: 788--799, 2012. Google ScholarDigital Library
- Y. Tian, R. A. Hankins, and J. M. Patel. Efficient aggregation for graph summarization. In SIGMOD, pages 567--580, 2008. Google ScholarDigital Library
- J. R. Ullmann. An algorithm for subgraph isomorphism. JACM, 23(1): 31--42, 1976. Google ScholarDigital Library
- N. Zhang, Y. Tian, and J. M. Patel. Discovery-driven graph summarization. In ICDE, 2010.Google ScholarCross Ref
- P. Zhao and J. Han. On graph query optimization in large networks. PVLDB, 3: 340--351, 2010. Google ScholarDigital Library
Index Terms
- Exploiting vertex relationships in speeding up subgraph isomorphism over large graphs
Recommendations
Polynomial-time algorithms for Subgraph Isomorphism in small graph classes of perfect graphs
Given two graphs, Subgraph Isomorphism is the problem of deciding whether the first graph (the base graph) contains a subgraph isomorphic to the second one (the pattern graph). This problem is NP-complete even for very restricted graph classes such as ...
Parallel Planar Subgraph Isomorphism and Vertex Connectivity
SPAA '20: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and ArchitecturesWe present the first parallel fixed-parameter algorithm for subgraph isomorphism in planar graphs, bounded-genus graphs, and, more generally, all minor-closed graphs of locally bounded treewidth. Our randomized low depth algorithm has a near-linear work ...
The subgraph isomorphism problem for outerplanar graphs
This paper deals with the subgraph isomorphism problem for outerplanar graphs (SUBOUTISOM). In general, since trees and forests are outerplanar, SUBOUTISOM is NP-complete. We show that SUBOUTISOM remains NP-complete even when the strongest connectivity ...
Comments