.png){kind=icon}
返回
A Twig-Based Algorithm for Top-k Subgraph Matching in Large-Scale Graph Data
.png){kind=icon}
PRE
AI
DOI：10.1016/j.bdr.2022.100350.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Subgraph matching aims to find similar substructures in a single graph according to a given query graph and is known as a basic query for graph data management. There exist many categories of subgraph matching solutions. Subgraph isomorphism, which is thought of an NP-complete problem, is an initial solution for the subgraph matching task. To speed up the procedure, graph simulation has been presented to match subgraphs with a polynomial complexity of time. Unfortunately, graph simulation usually loses topologies of matched subgraphs because of its loose restrictions. In this paper, we propose an approximation approach named kSGM (top -k Subraph Graph Matching) for subgraph matching based on twig patterns. First, we transform query graphs into twig patterns and match candidate substructures in graph data. Second, we present an optimized join strategy along with top -k mechanism, including join order selection based on cost evaluation and optimized pruning based on maximum/minimum possible score. Finally, we design experiments on real-life and synthetic graph data to evaluate the performance of our work. The results show that our proposed kSGM obviously reduces the time complexity and guarantee the correctness for answering the queries of subgraph matching compared to existing algorithms.(c) 2022 Elsevier Inc. All rights reserved.
Keyword:
Subgraph matching
Graph data
Twig patterns
Join optimization
Top-k mechanism
期刊
IF:
4.2
论文数:
416
被引数:
1.1K
机构
引用论文
分享收藏Mineralogy and crystal chemistry of Mn, Fe, Co, Ni, and Cu in a deep-sea Pacific polymetallic nodule
OAAI
OAAI分享收藏Optimised Anaesthesia to Reduce Post Operative Cognitive Decline (POCD) in Older Patients Undergoing Elective Surgery, a Randomised Controlled Trial.png)
PLoS ONEOAAI
PLoS ONEIF0
OAAI分享收藏Zwitterionic poly(2-oxazoline)s as promising candidates for blood contacting applicationsPolym. Chem.
Polym. Chem.IF0
PREAI
分享收藏
查看更多内容