PageRank的計算與更新研究.pdf

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

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

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