網(wǎng)頁鏈接分類的并行算法

　　1998年4月，在第七屆國際WWW（ World Wide Web）大會(huì)上，Page等提出了PageRank算法。這是一種基于網(wǎng)頁鏈接的排序算法，根據(jù)網(wǎng)頁之間的鏈接結(jié)構(gòu)來計(jì)算網(wǎng)頁的重要性，從而實(shí)現(xiàn)網(wǎng)頁排序。Google搜索引擎使用該算法對(duì)網(wǎng)頁進(jìn)行了準(zhǔn)確的排名。

　　隨著信息技術(shù)的發(fā)展，網(wǎng)頁數(shù)量急劇增加，采用串行PageRank算法迭代計(jì)算網(wǎng)頁排名時(shí)，需要消耗大量的存儲(chǔ)和計(jì)算資源，且計(jì)算效率相當(dāng)?shù)拖拢瑢で笠环N高效排名算法勢(shì)在必行。Hadoop是Apache公司提出的開源分布式計(jì)算框架，該框架下的MapReduce并行編程模型非常適合于海量數(shù)據(jù)的并行計(jì)算。

　　針對(duì)串行PageRank算法在處理海量網(wǎng)頁數(shù)據(jù)時(shí)效率低下的問題，提出一種基于網(wǎng)頁鏈接分類的PageRank并行算法。首先，將網(wǎng)頁按照網(wǎng)頁所屬網(wǎng)站分類，為來自不同站點(diǎn)的網(wǎng)頁設(shè)置不同的權(quán)重；其次，利用Hadoop并行計(jì)算框架，結(jié)合MapReduce分而治之的特點(diǎn)，并行計(jì)算網(wǎng)頁排名；最后，采用一種包含3層：數(shù)據(jù)層、預(yù)處理層、計(jì)算層的數(shù)據(jù)壓縮方法，對(duì)并行算法進(jìn)行優(yōu)化。實(shí)驗(yàn)結(jié)果表明，與串行PageRank算法相比，所提算法在最好情況下結(jié)果準(zhǔn)確率提高了12%，計(jì)算效率提高了33%。