Subgraph Matching with Set Similarity in a Large Graph Database

doi:10.1109/TKDE.2015.2391125

CORC > 北京大学 > 信息科学技术学院

	Subgraph Matching with Set Similarity in a Large Graph Database
	Hong, Liang ; Zou, Lei ; Lian, Xiang ; Yu, Philip S.
刊名	IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
	2015
关键词	Subgraph matching set similarity graph database index ISOMORPHISM ALGORITHM NETWORKS TOOL
DOI	10.1109/TKDE.2015.2391125
英文摘要	In real-world graphs such as social networks, Semantic Web and biological networks, each vertex usually contains rich information, which can be modeled by a set of tokens or elements. In this paper, we study a subgraph matching with set similarity (SMS2) query over a large graph database, which retrieves subgraphs that are structurally isomorphic to the query graph, and meanwhile satisfy the condition of vertex pair matching with the (dynamic) weighted set similarity. To efficiently process the SMS2 query, this paper designs a novel lattice-based index for data graph, and lightweight signatures for both query vertices and data vertices. Based on the index and signatures, we propose an efficient two-phase pruning strategy including set similarity pruning and structure-based pruning, which exploits the unique features of both (dynamic) weighted set similarity and graph topology. We also propose an efficient dominating-set-based subgraph matching algorithm guided by a dominating set selection algorithm to achieve better query performance. Extensive experiments on both real and synthetic datasets demonstrate that our method outperforms state-of-the-art methods by an order of magnitude.; National Science Foundation of China (NSFC) [61303025, 61370055]; Tencent; NSF [CNS-1115234, OISE-1129076]; US Department of Army [W911NF-12-1-0066]; Pinnacle Lab at Singapore Management University; SCI(E); EI; ARTICLE; hong@whu.edu.cn; zoulei@pku.edu.cn; lianx@utpa.edu; psyu@uic.edu; 9; 2507-2521; 27
语种	英语
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/416949]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Hong, Liang,Zou, Lei,Lian, Xiang,et al. Subgraph Matching with Set Similarity in a Large Graph Database[J]. IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,2015.
APA	Hong, Liang,Zou, Lei,Lian, Xiang,&Yu, Philip S..(2015).Subgraph Matching with Set Similarity in a Large Graph Database.IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING.
MLA	Hong, Liang,et al."Subgraph Matching with Set Similarity in a Large Graph Database".IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING (2015).