基于MapReduce的SimRank++算法研究與實(shí)現(xiàn).pdf

1、互聯(lián)網(wǎng)技術(shù)的發(fā)展使信息以前所未有的速度增長(zhǎng)和傳播。隨著網(wǎng)絡(luò)數(shù)據(jù)爆炸式的增長(zhǎng)，在網(wǎng)絡(luò)中快速、準(zhǔn)確地定位到自己想要查詢的信息成為Web搜索領(lǐng)域的一項(xiàng)挑戰(zhàn)。尤其是在贊助商廣告檢索系統(tǒng)中，由于用戶輸入的查詢短語通常較短并且廣告的競(jìng)價(jià)詞頻繁動(dòng)態(tài)變化，精準(zhǔn)地匹配到足夠數(shù)量且相關(guān)性好的廣告成為廣告檢索系統(tǒng)的一項(xiàng)技術(shù)難題。查詢重寫技術(shù)能夠?qū)υ疾樵冎貥?gòu)出一系列相似查詢，通過重構(gòu)出的相似查詢往往能夠提高系統(tǒng)的查全率和查準(zhǔn)率。
　　擴(kuò)展的SimRan

2、k(SimRank++)算法是一種較好的查詢重寫方法，其通過查詢點(diǎn)擊數(shù)據(jù)，能夠快速計(jì)算出兩兩查詢間的相似度。然而，原始的SimRank算法具有較高的時(shí)間和空間復(fù)雜度，并且由于實(shí)際的互聯(lián)網(wǎng)廣告檢索系統(tǒng)需要處理的數(shù)據(jù)規(guī)模非常龐大，因而難以對(duì)其直接應(yīng)用。
　　作為“云”計(jì)算的核心技術(shù)之一，MapReduce分布式并行編程模型為大規(guī)模數(shù)據(jù)處理帶來了方便，其通過“分而治之”的策略，把對(duì)數(shù)據(jù)集的大規(guī)模操作分發(fā)給網(wǎng)絡(luò)上的每個(gè)節(jié)點(diǎn)，然后通過整合各

3、節(jié)點(diǎn)的計(jì)算結(jié)果，得到最終的結(jié)果。在使用MapReduce編程模型時(shí)，待處理的數(shù)據(jù)集必須能夠分解為多個(gè)規(guī)模較小的數(shù)據(jù)集，并且每個(gè)小規(guī)模數(shù)據(jù)集的并行處理任務(wù)相互之間沒有依賴關(guān)系。因此，如何分解計(jì)算任務(wù)成為MapReduce編程的難點(diǎn)。
　　本文在對(duì)SimRank++算法和MapReduce編程模型深入研究的基礎(chǔ)上，給出了使用MapReduce框架實(shí)現(xiàn)SimRank++算法的方法，主要研究?jī)?nèi)容概括為以下3個(gè)方面：
　　(1)針對(duì)查

4、詢重寫任務(wù)，對(duì)SimRank++算法的計(jì)算公式進(jìn)行了優(yōu)化。通過矩陣轉(zhuǎn)置的等價(jià)變換，略去了原始計(jì)算公式中的轉(zhuǎn)移概率的轉(zhuǎn)置矩陣；同時(shí)，針對(duì)查詢-廣告二部圖的特性，把計(jì)算公式拆分成兩部分，各部分的規(guī)模大大降低，并且可以依次計(jì)算。
　　(2)給出了基于MapReduce編程模型的通用矩陣乘法運(yùn)算方法。通過矩陣的分塊，使得乘法運(yùn)算可以作用在較大的數(shù)據(jù)集上。給出了4種分塊乘法策略，有效地消除了任務(wù)間的相互依賴關(guān)系。本文還對(duì)4種策略的系統(tǒng)開銷進(jìn)