Graph pattern matching: A join/semijoin approach

	Graph pattern matching: A join/semijoin approach
	Cheng Jiefeng; Yu Jeffrey Xu; Yu Philip S.
刊名	IEEE transactions on knowledge and data engineering
	2011
卷号	23 期号:7 页码:1006-1021
英文摘要	Due to rapid growth of the Internet and new scientific/technological advances, there exist many new applications that model data as graphs, because graphs have sufficient expressiveness to model complicated structures. The dominance of graphs in real-world applications demands new graph processing techniques to access large data graphs effectively and efficiently. In this paper, we study a graph pattern matching problem, which is to find all patterns in a large data graph that match a user-given graph pattern. We propose new two-step R-join (reachability join) algorithms with a filter step (R-semijoin) and a fetch step (R-join) by utilizing a new cluster-based join index with graph codes in a relational database context. We also propose two optimization approaches to further optimize sequences of R-joins/R-semijoins. The first approach is based on R-join order selection followed by R-semijoin enhancement, and the second approach is to interleave R-joins with R-semijoins. We conducted extensive performance studies, and confirm the efficiency of our proposed new approaches.
收录类别	SCI
原文出处	http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5582090
语种	英语
内容类型	期刊论文
源URL	[http://ir.siat.ac.cn:8080/handle/172644/3546]
专题	深圳先进技术研究院_数字所
作者单位	IEEE transactions on knowledge and data engineering
推荐引用方式 GB/T 7714	Cheng Jiefeng；Yu Jeffrey Xu；Yu Philip S.. Graph pattern matching: A join/semijoin approach[J]. IEEE transactions on knowledge and data engineering,2011,23(7):1006-1021.
APA	Cheng Jiefeng；Yu Jeffrey Xu；Yu Philip S..(2011).Graph pattern matching: A join/semijoin approach.IEEE transactions on knowledge and data engineering,23(7),1006-1021.
MLA	Cheng Jiefeng；Yu Jeffrey Xu；Yu Philip S.."Graph pattern matching: A join/semijoin approach".IEEE transactions on knowledge and data engineering 23.7(2011):1006-1021.