The Anatomy of a Large-Scale Hypertextual Web

wangfans

随着Web的不断增长，这些任务变得越来越艰巨。然而硬件的性能和成本也在快速增长，可以部分抵消这些困难。然而，还有几个值得例外，如磁盘的寻道时间，操作系统的效率。在设计Google的过程中，我们既考虑了网络的增长速度，又考虑了技术的更新。Google的设计能够很好的升级处理超大量数据集。它能够高效地使用存储空间来存储索引。优化的数据结构能够快速有效地存取（请参见4.2节）。进一步，我们希望，相对于所抓取的文本文件和HTML网页的数量而言，存储和建立索引的代价尽可能的小（请参阅附录B）。对于象Google这样的集中式系统，采取这些措施得到了良好的系统可升级性。

wangfans

1. 3设计目标
1.3.1  改进搜索质量。
我们的主要目标是提高Web搜索引擎的质量。1994年，有人认为建立全搜索索引就有可能很容易找到任何东西。根据Best of the Web 1994 -- Navigators，“最佳导航服务应更容易找到几乎任何在网络上（已经输入的所有数据）。”。然而1997年的Web就迥然不同。任何最近使用搜索引擎的用户很容易证实索索引的完整性并不是唯一影响搜索引擎结果的因素。用户感兴趣的搜索结果往往被“垃圾结果”淹没。

wangfans

实际上，到1997年11月为止，四大商业搜索引擎中只有一个能够找到它自己（使用自己的搜索自己的名字时返回的前十个结果中有它自己）。导致这一问题的主要原因是文档的索引数目增加了好几个数量级，但是用户能够看的文档数却没有增加。人们仍然只希望看前面的几十个搜索结果。因此，当集合增大时，我们就需要高精确度的工具（在返回的前几十个结果中，相关文档的数量）。由于是从成千上万个有点相关的文档中选出几十个，实际上，我们希望相关的概念就是指最好的文档。高精确非常重要，甚至以响应（系统能够返回的有关文档的总数）为代价。令人十分乐观的的是利用超文本链接提供的信息有助于改进搜索和其它应用[Marchiori 97] [Spertus 97] [Weiss 96] [Kleinberg 98]。尤其是链接结构和链接文本，为相关性的判断和高质量筛选提供了大量的信息

wangfans

1.3.2  搜索引擎的学术研究
除了发展迅速，Web越来越商业化。到1993年，只有1.5%的网络服务是来自.com域名。到1997年，增长超过了60%。同时，搜索引擎从学术领域走进商业。到现在大多数搜索引擎被公司所有，很少发布技术细节。这就导致搜索引擎技术很大程度上仍然是暗箱操作，并倾向做广告（请参阅附录A）。对于Google来讲我们有一个的主要目标是推动学术领域在此方面的发展和了解。

wangfans

另一个设计目标是给适合数目的人们一个实用的系统。对我们来说应用十分重要，因为一些研究表明，现代网络系统中存在大量的有用数据。例如，每天有数千万个查询被执行。然而，获得这些数据却非常困难，主要因为它们被认为有商业价值。
我们的最终设计目标是构建一个体系结构，可以支持大型 Web数据上的一种新的研究活动。为了支持新研究，Google以压缩的形式保存了实际所抓到所有的文档。我们设计Google的主要目标之一就是要建立一个环境使其他研究者能够很快进入这个领域，处理海量网络数据，得到满意的结果，而通过其它方法却很难得到。系统在短时间内被建立起来，已经有几篇论文用到了Google建立的数据库，更多的在起步中。我们的另一个目标是建立一个宇宙空间实验室似的环境，在这里研究人员甚至学生都可以对我们的海量网络数据设计或做有趣的实验。

wangfans

2.系统功能
Google搜索引擎有两个重要功能，帮助它产生高精度的搜索结果。首先，应用Web的链接结构计算每个网页的质量等级值，这个等级称为PageRank，将在98页详细描述它。
第二点，Google利用超链接改进搜索结果

wangfans

2.1 PageRank：带来网页排序
网络的引用（链接）图形是重要的资源， 却没有被现有的大多搜索引擎使用。我们建立了一个包含518百万个超链接的图，它是一个具有重要意义的样本。这些图能够快速地计算网页的PageRank值，它是一个客观的标准，较好的符合人们主观的对一个网页重要程度的评价，由此对应的是，PageRank值是一个较好的区分通过网络搜索关键字获得的结果的方法。建立的基础是通过引用判断重要性。对于大多数的主题，一个简单的被限制为网页标题的文本匹配搜索当使用PageRank区分时得到了极好的结果（从google.stanford.edu可以得到演示）。对于Google主系统中的全文搜索，PageRank也有很大的帮助。

wangfans

2.1.1PageRank计算的描述：
文献引用理论应用到Web中，主要由引用或反向链接到给定页来计数。这会反映了该网页的重要性和质量的近似值。PageRank扩展了这种思想，不平等的计算所有页面上的链接并且通过一个页面上的所有链接。PageRank定义如下:
我们假设页面T1…Tn指向网页A（例如，被引用）。参数d是一个设定在0，1之间的制动因子。我们通常设置d为0.85。在下一节有更多关于d的详情，C（A）定义为网页A指向其它网页的链接数，网页A的PageRank值由下式给出：
PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

wangfans

请注意PageRank涵盖所有网页的一个概率分布得来，因此所有网页PageRank和是1。 PageRank或PR(A)可使用一个简单的迭代算法来计算，相应对应月网页链接矩阵的主特征向量。中等规模的网站计算26万网页的 PageRank值要花费几小时。还有一些技术细节超出了本文论述的范围。

wangfans

2.1.2 直觉的解释
PageRank被看作用户行为的模型。我们假想一个“随机上网者”；随机地给他一个网页；他漫无目的地命中网页的链接，而从来不点“返回键”；最终他觉得烦了，又从另一个随机的网页从新开始。随机访问一个网页的可能性就是它的PageRank值。制动因子d是随机访问一个网页烦了的可能性，随机另选一个网页。对单个网页或一组网页，一个重要的变量加入到制动因子d中。这允许个人可以故意地误导系统，以得到较高的PageRank值几乎变成不可能的。我们还有其它的PageRank算法，见98页。另外的直觉判断是一个网页有很多网页指向它，或者一些PageRank值高的网页指向它，则这个网页很重要。 直觉地，在Web中，一个网页被很多网页引用，那么这个网页值得一看。一个网页被象Yahoo这样重要的主页引用即使一次，也值得一看。如果一个网页的质量不高，或者是死链接，象Yahoo这样的主页不会链向它。PageRank处理了这两方面因素，并通过网络链接递归地传递。