SEOVIP学习社区

 找回密码
 注册
搜索
查看: 2425|回复: 0

Google 的秘密- PageRank 彻底解说 中文版 五

[复制链接]
  • TA的每日心情
    开心
    2011-7-12 09:45
  • 签到天数: 6 天

    [LV.2]偶尔看看I

    admin 发表于 2005-3-22 14:43:28 | 显示全部楼层 |阅读模式
    5. Namazu 上的实际安装实验
    <>为了使更简单地推测上文描述的问题,PageRank 并不是非世界所有的web页面而不能使用的考虑方法,即使是个人的利用方法也能实现。为了实现「Personalized PageRank」,针对在各种 UNIX 和 Windows 上运作的中小规模网站适用的全文检索系统 Namazu 进行了实际安装实验。(关于Namazu可参考 日语全文检索引擎软件列表。)</P>
    <>由于实验能简单地控制内存的使用量,并将最大特性值用1来考虑,所以将 Have liwala(1999)的想法做为基本的考虑方法。但是对 dangling pages 的处理有少许不同。固有矢量的计算内核使用了数值计算脚本 GNU Octave。所以基本的代码编写自己只用了一天就解决了。另外,从用 mknmz 编写的索引不能直接计算 PageRank,而要事前准备表示邻接关系的索引(邻接列表)。这个也有可能被编入检索者(Indexer)的主要部分。 </P>
    <>以下表示了实际计算时间(单位:秒)。运行机器的配置为 PentiumII 400MHz x 2,内存512MB,Kondara MNU/Linux 1.2的(kernel-2.2 .17-15ksmp),Octave-2.0.16(一般状态分发物)。收敛精度(剩余差矢量的L1规范)取了到1.0e-10,也许有些过分精确了。 </P>文书数N     mknmz时间    准备时间   PageRank计算时间
    ============================================================
    128          58          2          6
    2,301       1, 575       46         214
    49,604      15,975       478        5,872
    <>因为没用一些巨大的web页群来做测试,所以实验只停留在小规模的基础上。虽然有这个难点,但从基本上可以了解与索引所花的时间相比,在很短的时间里就可以计算 PageRank 的倾向吧。 </P>
    <>因为 Namazu 自身中也有很多难题,所以并不寄予很大的奢望,但至少使用 105 程度(尽可能 106)规模的web页面群来实验。从趋势来看可以预想 N=106 的计算时间恐怕会发散开去,所以在 N=106 时,若是能够讨论把mknmz时间变成和comparable一样的加速方法的话,对于Personalized PageRank 来说就十分实用了。作为参考,根据Page et al.(1998),Google 对7500万的URL的实际 PageRank 计算时间约是5小时。(2001年2月现在不明)。从这个角度来说,研究更加高效的加速法的余地就十分得必要了吧。 </P>
    <>计算实际运行时的使用内存最大也是10几MB左右。如果是Haveliwala (1999)那样的「吝啬地作战」的话,最大只有O(3N+2)左右的内存使用量就做完了,不过 N 是 104-5 程度和内存的使用量连 N2 也放不进的话,其他的也只能勉强调谐了,所以以 O(5N+α) (α是疏松行列的非零成分数字,典型的是5-20N左右) 程度来编写代码。另外 N 是103 左右时,可以确认不压缩疏松行列就在内存上使用幂乘法来计算,从速度面上来说是非常有利的。实测时速度为上述数字的6-7倍左右的。但遗憾的是,这个方法从内存的限制来看,尽可能地只使用2-3千页以内。 </P>
    <>此次我们使用了 Octave 分发附属的「Tsurushi」,不过,正像大家知道的那样,如果把 Octave 调谐的好的话,会戏剧性地提高完成的速度。Octave-2.1.x 和 ATLAS 的组合有时候根据情况甚至会使大规模行列乘法的运算速度提高10倍以上。 </P>
    <>实验的详细结果请参照prnmz-1.0.tar.gz 中的文档。 </P>
    Personalized PageRank 的基本性质
    <>人们经常会利用 MHonArc、latex2html 或者 PowerPoint 这样的工具将文档变成 HTML,针对这样的人工制作的HTML链接群求 PageRank 的话,大部分页面的得分几乎都是一样的(~1/N)。如果考虑邻接行列,则大部分的成分是1,或者对角成分附近全部是1。因为这样的推移概率行列的固有矢量成为(1,1,…,1)。 </P>
    <>或是象 sitemap.html 一样变成树状的情况下,分数会集中在sitemap.html中。就算占据全体的9成也不算新奇。 </P>
    <P>从现在起能说的是,为了计算有意义的 PageRank,要尽可能地排除机械生成的链接关系。如果把链接关系看做是推荐关系的话更加容易认同了吧。 </P>
    您需要登录后才可以回帖 登录 | 注册

    本版积分规则

    小黑屋|手机版|Archiver|SEOVIP学习社区

    GMT+8, 2024-3-29 16:11 , Processed in 0.034550 second(s), 21 queries .

    Powered by Discuz! X3.4

    Copyright © 2001-2021, Tencent Cloud.

    快速回复 返回顶部 返回列表