Using Graphics Processors for High Performance SimRank Computation
Using Graphics Processors for High Performance SimRank Computation
复制标题
使用图形处理器进行高性能 SimRank 计算
DOI：
10.1109/tkde.2011.91
复制
发表时间：
2012-09
影响因子：
8.9
通讯作者：
Guoming He, cuiping Li, Hong Chen, Xiaoyong DU, H
中科院分区：
文献类型：
--
作者：
Guoming He, cuiping Li, Hong Chen, Xiaoyong DU, H
最近，人们对基于图形的分析产生了浓厚的兴趣。基于图的分析最重要的方面之一是测量图中节点之间的相似性。SimRank是一种简单而有影响力的衡量标准，基于固体图形理论模型。然而，现有的SimRank计算方法存在两个局限性：1）实际计算成本可能非常高; 2）它们只能应用于静态图。在本文中，我们利用固有的并行性和高内存带宽的图形处理单元（GPU），以加速计算SimRank的大型图形。此外，基于SimRank本质上是一个一阶马尔可夫链的观察，我们建议利用迭代聚合技术解耦马尔可夫链并行计算SimRank分数的大型图。迭代聚合方法可以应用于动态图。此外，它不仅可以处理链路更新问题，而且节点更新问题。我们给出了相应的理论证明和分析，提出了三种优化策略以进一步提高计算效率，并将所提算法扩展到动态图。在人工数据集和真实的数据集上的大量实验验证了所提方法的有效性。
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. We give the corresponding theoretical justification and analysis, propose three optimization strategies to further improve the computation efficiency, and extend the proposed algorithm to dynamic graphs. Extensive experiments on synthetic and real data sets verify that the proposed methods are efficient and effective.
登录
查看更多内容
DOI：
10.1137/1.9781611972788.64
发表时间：
2008-10
期刊：
--
影响因子：
--
作者：
Hanghang Tong;S. Papadimitriou;Philip S. Yu;C. Faloutsos
通讯作者：
Hanghang Tong;S. Papadimitriou;Philip S. Yu;C. Faloutsos
DOI：
10.1145/1835804.1835874
发表时间：
2010-07
期刊：
Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining
影响因子：
--
作者：
Guoming He;Haijun Feng;Cuiping Li;Hong Chen
通讯作者：
Guoming He;Haijun Feng;Cuiping Li;Hong Chen
DOI：
10.1137/040619028
发表时间：
2005-12
期刊：
SIAM J. Matrix Anal. Appl.
影响因子：
--
作者：
A. Langville;C. D. Meyer
通讯作者：
A. Langville;C. D. Meyer
DOI：
10.1145/1013367.1013491
发表时间：
2004-05
期刊：
--
影响因子：
--
作者：
A. Langville;C. D. Meyer
通讯作者：
A. Langville;C. D. Meyer
DOI：
10.1145/1739041.1739098
发表时间：
2010-03
期刊：
--
影响因子：
--
作者：
Cuiping Li;Jiawei Han;Guoming He;Xin Jin;Yizhou Sun;Yintao Yu;Tianyi Wu
通讯作者：
Cuiping Li;Jiawei Han;Guoming He;Xin Jin;Yizhou Sun;Yintao Yu;Tianyi Wu