| 基于分解转移矩阵的PageRank迭代计算方法 |
| |
| 引用本文： | 刘松彬,都云程,施水才.基于分解转移矩阵的PageRank迭代计算方法[J].中文信息学报,2007,21(5):41-45. |
| |
| 作者姓名： | 刘松彬 都云程 施水才 |
| |
| 作者单位： | 北京信息科技大学 中文信息处理研究中心,北京 100101
|
| |
| 基金项目： | 国家高技术研究发展计划(863计划);北京市教委科技发展计划项目;北京市属市管高校人才强教计划 |
| |
| 摘 要： | 本文提出了一种基于分解转移矩阵的PageRank的迭代计算方法。该方法对PageRank理论模型进一步推导,把其Markov状态转移矩阵进行了分解,从而降低存储开销和计算复杂度,减少I/O需求,使得PageRank计算的工程化实现更为简单。实验表明1 700多万的网页2.8亿条链接,可以在30秒内完成一次迭代,内存需求峰值585MB,可以满足工程化应用的需求。
|
| 关 键 词： | 计算机应用 中文信息处理 PageRank 搜索引擎 Markov状态转移矩阵 矩阵分解 |
| 文章编号： | 1003-0077（2007）05-0041-05 |
| 收稿时间： | 2007-03-31 |
| 修稿时间： | 2007-03-312007-06-27 |
A Method of Computing PageRank Based on Transition Matrix Decomposition |
| |
| LIU Song-bin,DU Yun-cheng,SHI Shui-cai.A Method of Computing PageRank Based on Transition Matrix Decomposition[J].Journal of Chinese Information Processing,2007,21(5):41-45. |
| |
| Authors: | LIU Song-bin DU Yun-cheng SHI Shui-cai |
| |
| Affiliation: | Chinese Information Processing Research Center, Beijing Information Science & Technology University,
Beijing 100101, China
|
| |
| Abstract: | This paper proposes a method of computing PageRank based on transfer matrix decomposition.Based on the PageRank random surfer model,the method decomposes the Markov states transfer matrix,so that the memory cost,computational complexity and I/O needs are reduced drastically.Experiments show that each iteration can be completed in 30 seconds and that the peak memory demand is 585MB during the PageRank computation of 17 million Web Pages containing 280 million links,indicating that this method meets the demand for engineering applications. |
| |
| Keywords: | PageRank |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《中文信息学报》浏览原始摘要信息 |
|
点击此处可从《中文信息学报》下载全文 |
