图 书 馆
迭代聚集大图中的并行计算研究Parallel SimRank Computation on Large Graphs with Iterative Aggregation |
|
| 课程网址: | http://videolectures.net/kdd2010_he_psrclgia/ |
| 主讲教师: | Guoming He |
| 开课单位: | 中国人民大学 |
| 开课时间: | 2010-10-01 |
| 课程语种: | 汉简 |
| 中文简介: |  |
| 课程简介: | Recently there has been a lot of interest in graph-based analysis. One of the most important aspects of graph-based analysis is to measure similarity between nodes in a graph. SimRank is a simple and influential measure of this kind, based on a solid graph theoretical model. However, existing methods on SimRank computation suffer from two limitations: 1) the computing cost can be very high in practice; and 2) they can only be applied on static graphs. In this paper, we exploit the inherent parallelism and high memory bandwidth of graphics processing units (GPU) to accelerate the computation of SimRank on large graphs. Furthermore, based on the observation that SimRank is essentially a first-order Markov Chain, we propose to utilize the iterative aggregation techniques for uncoupling Markov chains to compute SimRank scores in parallel for large graphs. The iterative aggregation method can be applied on dynamic graphs. Moreover, it can handle not only the link-updating problem but also the node-updating problem. Extensive experiments on synthetic and real data sets verify that the proposed methods are efficient and effective. |
| 关 键 词: | 图论模型; 并行性; 图形处理单元; 马尔可夫链 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2019-12-21：lxf |
| 阅读次数: | 63 |