基于mapreducesimrank%2b%2b算法的研究和实现

《基于mapreducesimrank%2b%2b算法的研究和实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于MapReduce的SimRank++算法研究与实现中文摘要基于MapReduce的SimRank++算法研究与实现中文摘要互联网技术的发展使信息以前所未有的速度增长和传播。随着网络数据爆炸式的增长，在网络中快速、准确地定位到自己想要查询的信息成为Web搜索领域的一项挑战。尤其是在赞助商广告检索系统中，由于用户输入的查询短语通常较短并且广告的竞价词频繁动态变化，精准地匹配到足够数量且相关性好的广告成为广告检索系统的一项技术难题。查询重写技术能够对原始查询重构出一系列相似查询，通过重构出的相似查询往往能够提高系统的查全率和查准率

2、。扩展的SimRank(SimRank++)算法是一种较好的查询重写方法，其通过查询点击数据，能够快速计算出两两查询间的相似度。然而，原始的SimRank算法具有较高的时间和空间复杂度，并且由于实际的互联网广告检索系统需要处理的数据规模非常庞大，因而难以对其直接应用。作为“云”计算的核心技术之一，MapReduce分布式并行编程模型为大规模数据处理带来了方便，其通过“分而治之”的策略，把对数据集的大规模操作分发给网络上的每个节点，然后通过整合各节点的计算结果，得到最终的结果。在使用MapReduce编程模型时，待处理的数据集必须能

3、够分解为多个规模较小的数据集，并且每个小规模数据集的并行处理任务相互之间没有依赖关系。因此，如何分解计算任务成为MapReduce编程的难点。本文在对SimRank++算法和MapReduce编程模型深入研究的基础上，给出了使用MapReduce框架实现SimRank++算法的方法，主要研究内容概括为以下3个方面：(1)针对查询重写任务，对SimRank++算法的计算公式进行了优化。通过矩阵转置的等价变换，略去了原始计算公式中的转移概率的转置矩阵；同时，针对查询-广告二部图的特性，把计算公式拆分成两部分，各部分的规模大大降低，并且

4、可以依次计算。(2)给出了基于MapReduce编程模型的通用矩阵乘法运算方法。通过矩阵的分块，I中文摘要基于MapReduce的SimRank++算法研究与实现使得乘法运算可以作用在较大的数据集上。给出了4种分块乘法策略，有效地消除了任务间的相互依赖关系。本文还对4种策略的系统开销进行了分析和对比。(3)给出了使用MapReduce编程框架实现SimRank++算法的详细过程，主要包括权值矩阵和证据矩阵的计算、算法迭代步骤和相似度值归一化等步骤。同时，给出了一些可行的性能优化方法，主要包括：阈值过滤、自适应数据分片大小、Inpl

5、ace技术、中间结果压缩等。通过实验验证了本文所提方法的有效性，并分析矩阵乘法运算和SimRank++算法的性能。关键词：MapReduce，云计算，矩阵运算，信息检索，查询重写作者：张骏指导教师：吕强协助指导：王红玲IIResearchonSimRank++AlgorithmbasedonMapReduceFrameworkAbstractResearchonSimRank++AlgorithmbasedonMapReduceFrameworkAbstractBecauseofthedevelopmentofInternette

6、chnology,theinformationgrowsandspreadswithunprecedentedrate.Withtheexplosivegrowthofwebdata,itisdifficulttofindthedesiredinformationquicklyandaccuratelyinthefieldofWebsearch.Especiallyinthesponsoredsearcharea,theissuedqueriesareusuallyshortandthebidkeywordsofadvertise

7、mentschangedynamicallyandfrequently.Asaresult,itischallengingtofindenoughadvertisementswithhighrelevance.Queryrewritingtechniquecouldreformulateaseriesofsimilarquerieswithrespecttotheoriginalquery.Therecallandprecisionwouldbeimprovedwiththesereformulatedqueries.TheSim

8、Rank++algorithmisafinequeryrewritingmethod.Throughtheclick-throughdata,itcancomputethesimilaritybetweenanytwoqueries.However