Google 的秘密- PageRank

• 以下表示了实际计算时间(单位：秒)。运行机器的配置为 PentiumII 400MHz x 2,内存512MB，Kondara MNU/Linux 1.2的(kernel-2.2 .17-15ksmp)，Octave-2.0.16(一般状态分发物)。收敛精度(剩余差矢量的L1规范)取了到1.0e-10,也许有些过分精确了。

  文书数N     mknmz时间    准备时间   PageRank计算时间
  ============================================================
  128          58          2          6
  2,301       1, 575       46         214
  49,604      15,975       478        5,872  

  因为没用一些巨大的web页群来做测试，所以实验只停留在小规模的基础上。虽然有这个难点,但从基本上可以了解与索引所花的时间相比，在很短的时间里就可以计算 PageRank 的倾向吧。

  因为 Namazu 自身中也有很多难题，所以并不寄予很大的奢望，但至少使用 10⁵ 程度(尽可能 10⁶)规模的web页面群来实验。从趋势来看可以预想 N=10⁶ 的计算时间恐怕会发散开去，所以在 N=10⁶ 时，若是能够讨论把mknmz时间变成和comparable一样的加速方法的话，对于Personalized PageRank 来说就十分实用了。作为参考，根据Page et al.(1998)，Google 对7500万的URL的实际 PageRank 计算时间约是5小时。(2001年2月现在不明)。从这个角度来说，研究更加高效的加速法的余地就十分得必要了吧。

  计算实际运行时的使用内存最大也是10几MB左右。如果是Haveliwala (1999)那样的「吝啬地作战」的话，最大只有O(3N+2)左右的内存使用量就做完了,不过 N 是 10^4-5 程度和内存的使用量连 N² 也放不进的话，其他的也只能勉强调谐了，所以以 O(5N+α) (α是疏松行列的非零成分数字，典型的是5-20N左右) 程度来编写代码。另外 N 是10³ 左右时，可以确认不压缩疏松行列就在内存上使用幂乘法来计算，从速度面上来说是非常有利的。实测时速度为上述数字的6-7倍左右的。但遗憾的是，这个方法从内存的限制来看，尽可能地只使用2-3千页以内。

  此次我们使用了 Octave 分发附属的「Tsurushi」,不过，正像大家知道的那样，如果把 Octave 调谐的好的话，会戏剧性地提高完成的速度。Octave-2.1.x 和 ATLAS 的组合有时候根据情况甚至会使大规模行列乘法的运算速度提高10倍以上。

  实验的详细结果请参照prnmz-1.0.tar.gz 中的文档。

  Personalized PageRank 的基本性质

  人们经常会利用 MHonArc、latex2html 或者 Powerpoint 这样的工具将文档变成 HTML，针对这样的人工制作的HTML链接群求 PageRank 的话，大部分页面的得分几乎都是一样的(～1/N)。如果考虑邻接行列，则大部分的成分是1，或者对角成分附近全部是1。因为这样的推移概率行列的固有矢量成为(1,1,…,1)。

  或是象 sitemap.html 一样变成树状的情况下，分数会集中在sitemap.html中。就算占据全体的9成也不算新奇。

  从现在起能说的是，为了计算有意义的 PageRank，要尽可能地排除机械生成的链接关系。如果把链接关系看做是推荐关系的话更加容易认同了吧。

  6.对 PageRank 的个人的见解

  (读者)应该没有余地去怀疑象 PageRank 那样利用超级链接来决定排列次序有效手法吧。

• 上一页 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] 下一页 
• 复制本页网址和标题，发送给你QQ/Msn的好友一起分享
  
  
• Google 的秘密- PageRank 相关文章：
• ·Google 的秘密- PageRank
• Google 的秘密- PageRank 相关软件

上一篇:首份中国第三方Blog调查报告启示录

下一篇:网站优化工具集

• 特别声明：本站除部分特别声明禁止转载的专稿外的其他文章可以自由转载，但请务必注明出处和原始作
• 者.文章版权归文章原始作者所有.对于被本站转载文章的个人和网站，我们表示深深的谢意。如果本站转
• 载的文章有版权问题请联系编辑人员,我们尽快予以更正. 转载请注明来源：http://www.hackhome.com

精品推荐

热点TOP10

特别推荐