TBSGM: A Fast Subgraph Matching Method on Large Scale Graphs

Fusheng Jin, Yifeng Yang, Shuliang Wang, Ye Xue and Zhen Yan
Additional contact information
Fusheng Jin: Beijing Institute of Technology, Beijing, China
Yifeng Yang: Beijing Institute of Technology, Beijing, China
Shuliang Wang: School of Software, Beijing Institute of Technology, Beijing, China
Ye Xue: Northwestern University, Evanston, USA
Zhen Yan: Technical University of Munich, Munich, Germany

International Journal of Data Warehousing and Mining (IJDWM), 2018, vol. 14, issue 4, 67-89

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.

Date: 2018
References: Add references at CitEc
Citations:

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 018/IJDWM.2018100104 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jdwm00:v:14:y:2018:i:4:p:67-89

Access Statistics for this article

International Journal of Data Warehousing and Mining (IJDWM) is currently edited by Eric Pardede

More articles in International Journal of Data Warehousing and Mining (IJDWM) from IGI Global
Bibliographic data for series maintained by Journal Editor ().