Efficient Graph Similarity Search Over Large Graph Databases

doi:10.1109/TKDE.2014.2349924

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

	Efficient Graph Similarity Search Over Large Graph Databases
	Zheng, Weiguo ; Zou, Lei ; Lian, Xiang ; Wang, Dong ; Zhao, Dongyan
刊名	ieee知识与数据工程汇刊
	2015
关键词	Graph edit distance lower bound graph database graph similarity search EDIT DISTANCE COMMON SUBGRAPH ALGORITHM QUERIES REACHABILITY ISOMORPHISM JOINS TOOL
DOI	10.1109/TKDE.2014.2349924
英文摘要	Since many graph data are often noisy and incomplete in real applications, it has become increasingly important to retrieve graphs g in the graph database D that approximately match the query graph q, rather than exact graph matching. In this paper, we study the problem of graph similarity search, which retrieves graphs that are similar to a given query graph under the constraint of graph edit distance. We propose a systematic method for edit-distance based similarity search problem. Specifically, we derive two lower bounds, i.e., partition-based and branch-based bounds, from different perspectives. More importantly, a hybrid lower bound incorporating both ideas of the two lower bounds is proposed, which is theoretically proved to have higher (at least not lower) pruning power than using the two lower bounds together. We also present a uniform index structure, namely u-tree, to facilitate effective pruning and efficient query processing. Extensive experiments confirm that our proposed approach outperforms the existing approaches significantly, in terms of both the pruning power and query response time.; http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000351393500007&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=8e1609b174ce4e31116a60747a720701 ; Computer Science, Artificial Intelligence; Computer Science, Information Systems; Engineering, Electrical & Electronic; SCI(E); EI; 5; ARTICLE; zhengweiguo@pku.edu.cn; zoulei@pku.edu.cn; lianx@utpa.edu; wangd@pku.edu.cn; zhaody@pku.edu.cn; 4; 964-978; 27
语种	英语
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/161723]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Zheng, Weiguo,Zou, Lei,Lian, Xiang,et al. Efficient Graph Similarity Search Over Large Graph Databases[J]. ieee知识与数据工程汇刊,2015.
APA	Zheng, Weiguo,Zou, Lei,Lian, Xiang,Wang, Dong,&Zhao, Dongyan.(2015).Efficient Graph Similarity Search Over Large Graph Databases.ieee知识与数据工程汇刊.
MLA	Zheng, Weiguo,et al."Efficient Graph Similarity Search Over Large Graph Databases".ieee知识与数据工程汇刊 (2015).