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). |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论