QQ客服 官方微博 反馈留言

	Top-k graph pattern matching over large graphs
	Jiefeng Cheng; Xianggang Zeng; Jeffrey Xu Yu
	2013
会议名称	29th International Conference on Data Engineering, ICDE 2013
会议地点	Brisbane, QLD, Australia
英文摘要	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 pattern query (kGPM), 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 kGPM provides much more flexibility for a user to search graphs. And the problem itself is challenging. In this paper, we propose a new framework of processing kGPM with on-the-fly ranked lists based on spanning trees of the cyclic graph query. We observe a multidimensional representation for using multiple ranked lists to answer a given kGPM query. Under this representation, we propose a cost model to estimate the least number of tree answers to be consumed in each ranked list for a given kGPM query. This leads to a query optimization approach for kGPM processing, and a top-k algorithm to process kGPM with the optimal query plan. We conducted extensive performance studies using a synthetic dataset and a real dataset, and we confirm the efficiency of our proposed approach.
收录类别	EI
语种	英语
内容类型	会议论文
源URL	[http://ir.siat.ac.cn:8080/handle/172644/5102]
专题	深圳先进技术研究院_数字所
作者单位	2013
推荐引用方式 GB/T 7714	Jiefeng Cheng,Xianggang Zeng,Jeffrey Xu Yu. Top-k graph pattern matching over large graphs[C]. 见:29th International Conference on Data Engineering, ICDE 2013. Brisbane, QLD, Australia.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。