Top-k graph pattern matching: A twig query approach

	Top-k graph pattern matching: A twig query approach
	Xianggang Zeng; Jiefeng Cheng; Jeffrey Xu Yu; Shengzhong Feng
刊名	Web-Age Information Management Lecture Notes in Computer Science
	2012
英文摘要	There exist many graph-based applications including bioinformatics, social science, link analysis, citation analysis, and collaborative work. All need to deal with a large data graph. Given a large data graph, in this paper, we study finding top- k answers for a graph query, and in particular, we focus on top- k cyclic graph queries where a graph query is cyclic and can be complex. The capability of supporting top- k cyclic graph queries over a data graph provides much more flexibility for a user to search graphs. And the problem itself is challenging. After investigating a direct yet infeasible solution, we propose a new twig query approach. In our approach, we first identify a spanning tree of the cyclic graph query, which is used to generate a list of ranked twig answers on-demand. Then we identify the top- k answers for the graph query based on the twig answer list. In order to find the best twig query in solving a given cyclic graph query, cost-based optimization for twig query selection is studied. We conducted extensive performance studies using a real dataset, and we report our findings in this paper.
收录类别	EI
原文出处	http://link.springer.com/chapter/10.1007/978-3-642-32281-5_28
语种	英语
内容类型	期刊论文
源URL	[http://ir.siat.ac.cn:8080/handle/172644/4157]
专题	深圳先进技术研究院_数字所
作者单位	Web-Age Information Management Lecture Notes in Computer Science
推荐引用方式 GB/T 7714	Xianggang Zeng,Jiefeng Cheng,Jeffrey Xu Yu,et al. Top-k graph pattern matching: A twig query approach[J]. Web-Age Information Management Lecture Notes in Computer Science,2012.
APA	Xianggang Zeng,Jiefeng Cheng,Jeffrey Xu Yu,&Shengzhong Feng.(2012).Top-k graph pattern matching: A twig query approach.Web-Age Information Management Lecture Notes in Computer Science.
MLA	Xianggang Zeng,et al."Top-k graph pattern matching: A twig query approach".Web-Age Information Management Lecture Notes in Computer Science (2012).