基于mapreduce的simrank算法研究與實現(xiàn)

1、碩士學(xué)位論文論文題目基于MapReduce的SimRank算法研究與實現(xiàn)研究生姓名張駿指導(dǎo)教師姓名呂強（教授）專業(yè)名稱計算機應(yīng)用技術(shù)研究方向數(shù)據(jù)挖掘論文提交日期2012年10月基于MapReduce的SimRank算法研究與實現(xiàn)中文摘要I基于MapReduce的SimRank算法研究與實現(xiàn)中文摘要互聯(lián)網(wǎng)技術(shù)的發(fā)展使信息以前所未有的速度增長和傳播。隨著網(wǎng)絡(luò)數(shù)據(jù)爆炸式的增長，在網(wǎng)絡(luò)中快速、準(zhǔn)確地定位到自己想要查詢的信息成為Web搜索領(lǐng)域的一

2、項挑戰(zhàn)。尤其是在贊助商廣告檢索系統(tǒng)中，由于用戶輸入的查詢短語通常較短并且廣告的競價詞頻繁動態(tài)變化，精準(zhǔn)地匹配到足夠數(shù)量且相關(guān)性好的廣告成為廣告檢索系統(tǒng)的一項技術(shù)難題。查詢重寫技術(shù)能夠?qū)υ疾樵冎貥?gòu)出一系列相似查詢，通過重構(gòu)出的相似查詢往往能夠提高系統(tǒng)的查全率和查準(zhǔn)率。擴展的SimRank(SimRank)算法是一種較好的查詢重寫方法，其通過查詢點擊數(shù)據(jù)，能夠快速計算出兩兩查詢間的相似度。然而，原始的SimRank算法具有較高的時間和空間

3、復(fù)雜度，并且由于實際的互聯(lián)網(wǎng)廣告檢索系統(tǒng)需要處理的數(shù)據(jù)規(guī)模非常龐大，因而難以對其直接應(yīng)用。作為“云”計算的核心技術(shù)之一，MapReduce分布式并行編程模型為大規(guī)模數(shù)據(jù)處理帶來了方便，其通過“分而治之”的策略，把對數(shù)據(jù)集的大規(guī)模操作分發(fā)給網(wǎng)絡(luò)上的每個節(jié)點，然后通過整合各節(jié)點的計算結(jié)果，得到最終的結(jié)果。在使用MapReduce編程模型時，待處理的數(shù)據(jù)集必須能夠分解為多個規(guī)模較小的數(shù)據(jù)集，并且每個小規(guī)模數(shù)據(jù)集的并行處理任務(wù)相互之間沒有依賴關(guān)

4、系。因此，如何分解計算任務(wù)成為MapReduce編程的難點。本文在對SimRank算法和MapReduce編程模型深入研究的基礎(chǔ)上，給出了使用MapReduce框架實現(xiàn)SimRank算法的方法，主要研究內(nèi)容概括為以下3個方面：(1)針對查詢重寫任務(wù)，對SimRank算法的計算公式進行了優(yōu)化。通過矩陣轉(zhuǎn)置的等價變換，略去了原始計算公式中的轉(zhuǎn)移概率的轉(zhuǎn)置矩陣；同時，針對查詢廣告二部圖的特性，把計算公式拆分成兩部分，各部分的規(guī)模大大降低，并且