Top-k shortest distance join over large graph

	Top-k shortest distance join over large graph
	Chunguang YE; Jiefeng CHENG; Shengzhong FENG
刊名	Journal of Computational Information Systems
	2013
英文摘要	Large graphs appear very frequently in numerous applications nowadays. In this paper, we study a new problem, called top-$k$ shortest distance join. Given a graph and two sets of vertices $A$ and $B$, the answer to this problem consists of $k$ pairs from $A \times B$ which have the top-$k$ shortest distances among all such pairs. It is an elementary problem and act as the foundation for many other high level graph problems. The naive solution as $\|A\| \cdot \|B\| $ times of evaluations, cannot achieve satisfactory performance, especially when $\|A\|$ or $\|B\|$ is large. In this paper, we propose a new approach which performs a batch processing in order to share the cost. To fully exploit the fact that only the first $k$ shortest distances are required, we further develop on-demand processing based on the dynamic programming search strategy. An extensive experimental evaluation on both real and synthetic datasets demonstrates the efficiency of our approach.
收录类别	EI
原文出处	http://www.jofcis.com/publishedpapers/2013_9_15_6285_6295.pdf
语种	英语
内容类型	期刊论文
源URL	[http://ir.siat.ac.cn:8080/handle/172644/5057]
专题	深圳先进技术研究院_数字所
作者单位	Journal of Computational Information Systems
推荐引用方式 GB/T 7714	Chunguang YE,Jiefeng CHENG,Shengzhong FENG. Top-k shortest distance join over large graph[J]. Journal of Computational Information Systems,2013.
APA	Chunguang YE,Jiefeng CHENG,&Shengzhong FENG.(2013).Top-k shortest distance join over large graph.Journal of Computational Information Systems.
MLA	Chunguang YE,et al."Top-k shortest distance join over large graph".Journal of Computational Information Systems (2013).