|
|||||
|
|
| Asyn-SimRank：一种可异步执行的大规模 SimRank 算法 | |
| 引用本文： | 王春磊,张岩峰,鲍玉斌,赵长宽,于戈,高立新.Asyn-SimRank：一种可异步执行的大规模 SimRank 算法[J].计算机研究与发展,2015(7). |
| 作者姓名： | 王春磊 张岩峰 鲍玉斌 赵长宽 于戈 高立新 |
| 作者单位： | 1. 东北大学信息科学与工程学院计算机软件研究所 沈阳 110819 2. 东北大学计算中心 沈阳 110819 3. 美国麻州大学阿默斯特校区电子与计算机工程系 美国阿默斯特 01003 |
| 基金项目： | 国家自然科学基金项目(61300023，61272179，61033007，61173028)；中央高校基本科研业务费基金项目(N120416001， N120816001)；中国移动基金项目(MCM20122051)；辽宁省科技计划基金项目 |
| 摘 要： | SimRank 算法利用网络结构来评估网络中任意2点的相似性，它被广泛应用于社交网络和链接预测等诸多领域中．近年来，随着大数据技术的发展，SimRank 算法处理的数据不断增大，人们利用MapReduce 等分布式计算模型设计实现分布式的大规模 SimRank 算法来适应大数据处理的需求．但是，由于 SimRank 算法包含开销较大的迭代过程，每次迭代之后都需要一个全局同步，且每次迭代的计算复杂度高、通信量大，SimRank 算法不能在分布式环境下高效地实现．1）提出 Asyn‐SimRank 算法，该算法采用迭代‐累积的方式完成迭代计算，异步执行 SimRank 的核心迭代过程，避免了大规模分布式计算中的大量同步开销，同时有效降低计算量并减少通信开销；2）提出关键点优先调度计算，提升了 Asyn‐SimRank 算法的全局收敛速度；3）证明了 Asyn‐SimRank 算法的正确性和收敛性以及关键点优先调度计算的有效性；4）支持异步迭代的分布式框架 Maiter 上实现了 Asyn‐SimRank 算法．实验结果显示，相比较于 Hadoop ，Spark 上实现的 SimRank 算法和 Delta‐SimRank 算法，Asyn‐SimRank 算法大大提升了算法的计算效率，加速了算法收敛． |
| 关 键 词： | 异步计算 迭代计算 Asyn-SimRank 算法 相似度 大数据 MapReduce 模型 Maiter 框架 |
Asyn-SimRank：An Asynchronous Large-Scale SimRank Algorithm |
|
| Wang Chunlei,Zhang Yanfeng,Bao Yubin,Zhao Changkuan,Yu Ge,Gao Lixin.Asyn-SimRank：An Asynchronous Large-Scale SimRank Algorithm[J].Journal of Computer Research and Development,2015(7). | |
| Authors: | Wang Chunlei Zhang Yanfeng Bao Yubin Zhao Changkuan Yu Ge Gao Lixin |
| Abstract: | |
| Keywords: | asynchronous computation iterative computation Asyn-SimRank similarity big data MapReduce Maiter |
| 本文献已被 万方数据 等数据库收录！ | |