TBSGM: A fast subgraph matching method on large scale graphs

Fusheng Jin, Yifeng Yang, Shuliang Wang, Ye Xue, Zhen Yan

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)
Plum Print visual indicator of research metrics
  • Citations
    • Citation Indexes: 2
  • Captures
    • Readers: 1
see details

Abstract

Subgraph matching, which belongs to NP-hard, faces significant challenges on a large scale graph with billions of nodes, and existing methods are usually confronted with greater challenges from both stability and efficiency. In this article, a subgraph matching method in a distributed system, tree model-based subgraph matching method (TBSGM) is proposed. The authors provide a transformed efficient query tree as a replacement for a query graph. In order to get the tree, they present a cost evaluation model which may help to generate the efficient query tree according to network communication-cost and calculation-cost evaluation. Also, a key set based indexing strategy for intermediate results is given to simplify the matching results during network communication. Extensive experiments with real-world datasets show that TBSGM significantly outperforms other methods in the aspects of scalability and efficiency.

Original languageEnglish
Pages (from-to)67-89
Number of pages23
JournalInternational Journal of Data Warehousing and Mining
Volume14
Issue number4
DOIs
Publication statusPublished - 1 Oct 2018

Keywords

  • Efficient Query Tree
  • Indexing Strategy
  • Large Scale Graph
  • Subgraph Matching

Fingerprint

Dive into the research topics of 'TBSGM: A fast subgraph matching method on large scale graphs'. Together they form a unique fingerprint.

Cite this

Jin, F., Yang, Y., Wang, S., Xue, Y., & Yan, Z. (2018). TBSGM: A fast subgraph matching method on large scale graphs. International Journal of Data Warehousing and Mining, 14(4), 67-89. https://doi.org/10.4018/IJDWM.2018100104