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). |
入库方式： OAI收割
来源：深圳先进技术研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。