文献类型：期刊文章

作　　者：王春磊[1] 张岩峰[2] 鲍玉斌[1] 赵长宽[2] 于戈[1] 高立新[3]

机构地区：[1]东北大学信息科学与工程学院计算机软件研究所,沈阳110819 [2]东北大学计算中心,沈阳110819 [3]美国麻州大学阿默斯特校区电子与计算机工程系,美国阿默斯特01003

出　　处：《计算机研究与发展》

基　　金：国家自然科学基金项目(61300023;61272179;61033007;61173028);中央高校基本科研业务费基金项目(N120416001;N120816001);中国移动基金项目(MCM20122051);辽宁省科技计划基金项目(2013217004)

年　　份：2015

卷　　号：52

期　　号：7

起止页码：1567-1579

语　　种：中文

收录情况：AJ、BDHX、BDHX2014、CSA-PROQEUST、CSCD、CSCD2015_2016、EI、IC、JST、RCCSE、SCOPUS、ZGKJHX、核心刊

摘　　要：SimRank算法利用网络结构来评估网络中任意2点的相似性,它被广泛应用于社交网络和链接预测等诸多领域中.近年来,随着大数据技术的发展,SimRank算法处理的数据不断增大,人们利用MapReduce等分布式计算模型设计实现分布式的大规模SimRank算法来适应大数据处理的需求.但是,由于SimRank算法包含开销较大的迭代过程,每次迭代之后都需要一个全局同步,且每次迭代的计算复杂度高、通信量大,SimRank算法不能在分布式环境下高效地实现.1)提出Asyn-SimRank算法,该算法采用迭代-累积的方式完成迭代计算,异步执行SimRank的核心迭代过程,避免了大规模分布式计算中的大量同步开销,同时有效降低计算量并减少通信开销;2)提出关键点优先调度计算,提升了AsynSimRank算法的全局收敛速度;3)证明了Asyn-SimRank算法的正确性和收敛性以及关键点优先调度计算的有效性;4)支持异步迭代的分布式框架Maiter上实现了Asyn-SimRank算法.实验结果显示,相比较于Hadoop,Spark上实现的SimRank算法和Delta-SimRank算法,Asyn-SimRank算法大大提升了算法的计算效率,加速了算法收敛.

关 键 词：异步计算  迭代计算 Asyn-SimRank算法  相似度 大数据 MAPREDUCE模型 Maiter框架  

分 类 号：TP301.6]