PageRank的計(jì)算與更新研究.pdf

1、以Google為代表的當(dāng)代互聯(lián)網(wǎng)搜索引擎，將計(jì)算機(jī)理論研究與工程開(kāi)發(fā)完美結(jié)合，創(chuàng)造了非凡的用戶體驗(yàn)和文化。Google使用PageRank作為衡量網(wǎng)頁(yè)質(zhì)量的一個(gè)重要標(biāo)準(zhǔn)，取得了巨大成功。在當(dāng)前互聯(lián)網(wǎng)繼續(xù)蓬勃發(fā)展的情況下，PageRank的計(jì)算將涉及到海量的數(shù)據(jù)處理；另外，個(gè)性化搜索引擎是當(dāng)代搜索引擎的一個(gè)重要的發(fā)展方向，需要根據(jù)每個(gè)用戶的特征計(jì)算個(gè)性化的PageRank；因此迫切需要找到一個(gè)高效的PageRank計(jì)算和更新方法，來(lái)提高P

2、ageRank的計(jì)算和更新效率。 本文以PageRank的基本理論--隨機(jī)沖浪模型為基礎(chǔ)，進(jìn)行深入的理論的分析，做出進(jìn)一步理論推導(dǎo)，將Markov狀態(tài)轉(zhuǎn)移矩陣分解成三部分；計(jì)算時(shí)對(duì)每一部分分別處理，顯著降低了存儲(chǔ)開(kāi)銷(xiāo)(磁盤(pán)空間和內(nèi)存空間)和計(jì)算復(fù)雜度；使得PageRank的工程化計(jì)算變得比較簡(jiǎn)單，可以在普通配置的PC機(jī)上高效地完成千萬(wàn)級(jí)網(wǎng)頁(yè)的PageRank計(jì)算。 PageRank計(jì)算所涉及的Markov過(guò)程有其自身的特

3、殊性，世界各學(xué)者針對(duì)其特殊性提出了多種優(yōu)化途徑；本文分析了若干主要的優(yōu)化方法，并將其組合起來(lái)應(yīng)用，實(shí)驗(yàn)證明可以更大程度地提高PageRank的計(jì)算速度。 鑒于PageRank的計(jì)算代價(jià)太大，本文嘗試性地探尋一種針對(duì)工程化應(yīng)用的輕量級(jí)的更新策略，降低更新代價(jià)，提高更新速度。 本文所涉及的PageRank計(jì)算研究?jī)H限于單機(jī)處理，但矩陣運(yùn)算天然具有良好的并發(fā)性，在本文的計(jì)算過(guò)程和優(yōu)化過(guò)程中也保留了這個(gè)重要特性；所以下一步的一個(gè)