基于随机游走路径的分布式SimRank算法

摘要：

SimRank算法是一种常用的相似性度量模型，它基于图的拓扑结构信息来衡量任意两个对象之间的相似程度。随着数据规模的不断增大，集中式SimRank算法已不适用，而已有的分布式SimRank算法在运行效率和扩展性等方面存在缺陷。针对上述问题，提出了一种两阶段的基于随机游走路径的分布式SimRank算法。第一阶段基于BSP（bulk synchronous parallel）模型建立随机游走路径索引信息，支持新路径的动态添加，并通过阈值过滤尽可能减少生成路径的数量；第二阶段利用第一阶段生成的索引信息，提出了基于MapReduce的分布式SimRank算法。最后，通过实验验证了算法的可行性和有效性。

关键词：分布式SimRank、随机游走路径、BSP模型、MapReduce

分类号：TP391(计算技术、计算机技术)

资助基金：The National Natural Science Foundation of China under Grant Nos.61472070,61033007;the National Basic Research Program of China under Grant No.2012CB316201国家重点基础研究发展计划973计划;the Fundamental Research Funds for the Central Universities of China under Grant Nos.110404007,130404015;the Spe-cialized Research Fund for the Doctoral Program of Higher Education of China under Grant No.20120042110028;the MOE-Intel Special Fund of Information Technology under Grant No. MOE-INTEL-2012-06

在线出版日期：2015-01-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：1422-1431