对于大型搜索引擎的学术上的研究却很少。此外，由于技术上的突飞猛进和网页的急剧增加，在当前，创建一个搜索引擎和三年前已不可同日而语。本文提供了一种深入的描述，
与Web增殖快速进展今日创建Web搜索引擎是三年前很大不同。本文提供了到目前为止，对于我们大型的网页所搜引擎的深入的描述，这是第一个这样详细的公共描述。
除了如何把传统的搜索技术扩展到前所未有的海量数据，还有新的技术挑战涉及到了使用超文本中存在的其他附加信息产生更好的搜索结果。本文解决这样一个问题，如何建立一个可以利用超文本中存在的其他附加信息的实用的大型系统，同时我们也研究一下如何有效处理任何人都能发布他们想发布的包含任何信息的大量自由链接的问题。
1.1网络搜索引擎—升级换代：1994-2000
搜索引擎技术不得不快速升级跟上成倍增长的网站数量。1994年，第一个Web搜索引擎，WorldWideWebWorm(WWWW)拥有110，000个网页和网站可访问文档的索引。到1994年11月，顶级的搜索引擎声称可以检索到2万(WebCrawler)100万个网络文件(来自搜索引擎监视)。可以预见到2000年，可检索到的网页将超过10亿。同时，搜索引擎的访问量也会以惊人的速度增长。在1997年的三四月份，WorldWideWebWorm平均每天收到1500个查询。在1997年11月，Altavista声称它每天要处理大约20’百万个查询。随着网络用户的增长，可以预见到到2000年，自动搜索引擎每天将处理上亿个查询。我们系统的设计目标要解决许多问题，包括质量和可升级性，引入升级搜索引擎技术，把它升级到如此大量的数据上。
1.2Google：升级与网络
建立一个能够和当今web规模相适应的搜索引擎会面临许多挑战。抓网页技术必须足够快并且保持是最新的版本。存储空间必须高效的存储索引和文档。索引系统必须能够高效地处理上百亿GB的数据。处理查询必须快，达到每秒能处理成百上千个查询
1.3设计目标
1.3.1改进搜索质量。
1.3.2搜索引擎的学术研究
另一个设计目标是给适合数目的人们一个实用的系统。对我们来说应用十分重要，因为一些研究表明，现代网络系统中存在大量的有用数据。例如，每天有数千万个查询被执行。然而，获得这些数据却非常困难，主要因为它们被认为有商业价值。
Google搜索引擎有两个重要功能，帮助它产生高精度的搜索结果。首先，应用Web的链接结构计算每个网页的质量等级值，这个等级称为PageRank，将在98页详细描述它。
第二点，Google利用超链接改进搜索结果。
2.1PageRank：带来网页排序
网络的引用(链接)图形是重要的资源，却没有被现有的大多搜索引擎使用。我们建立了一个包含518百万个超链接的图，它是一个具有重要意义的样本。这些图能够快速地计算网页的PageRank值，它是一个客观的标准，较好的符合人们主观的对一个网页重要程度的评价，由此对应的是，PageRank值是一个较好的区分通过网络搜索关键字获得的结果的方法。建立的基础是通过引用判断重要性。对于大多数的主题，一个简单的被限制为网页标题的文本匹配搜索当使用PageRank区分时得到了极好的结果(从google.stanford.edu可以得到演示)。对于Google主系统中的全文搜索，PageRank也有很大的帮助。
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))
请注意PageRank涵盖所有网页的一个概率分布得来，因此所有网页PageRank和是1。PageRank或PR(A)可使用一个简单的迭代算法来计算，相应对应月网页链接矩阵的主特征向量。中等规模的网站计算26万网页的PageRank值要花费几小时。还有一些技术细节超出了本文论述的范围。
2.1.2直觉的解释
PageRank被看作用户行为的模型。我们假想一个“随机上网者”;随机地给他一个网页;他漫无目的地命中网页的链接，而从来不点“返回键”;最终他觉得烦了，又从另一个随机的网页从新开始。随机访问一个网页的可能性就是它的PageRank值。制动因子d是随机访问一个网页烦了的可能性，随机另选一个网页。对单个网页或一组网页，一个重要的变量加入到制动因子d中。这允许个人可以故意地误导系统，以得到较高的PageRank值几乎变成不可能的。我们还有其它的PageRank算法，见98页。另外的直觉判断是一个网页有很多网页指向它，或者一些PageRank值高的网页指向它，则这个网页很重要。直觉地，在Web中，一个网页被很多网页引用，那么这个网页值得一看。一个网页被象Yahoo这样重要的主页引用即使一次，也值得一看。如果一个网页的质量不高，或者是死链接，象Yahoo这样的主页不会链向它。PageRank处理了这两方面因素，并通过网络链接递归地传递。
2.2链接描述文字
我们的搜索引擎对链接文本进行了特殊的处理。大多数搜索引擎把链接文字和它所链向的网页联系起来。另外，把它和链接所指向的网页联系起来。这有几点好处。第一，通常链接描述文字比网页本身更精确地描述该网页。第二，链接描述文字可能链向的文档不能被文本搜索引擎检索到，例如图像，程序和数据库。有可能使返回的网页不能被抓到。注意那抓不到的网页将会带来一些问题。在返回给用户前检测不了它们的有效性。这种情况搜索引擎可能返回一个根本不存在的网页，但是有超级链接指向它。然而这种结果可以被挑出来的，所以此类的问题很少发生。
链接描述文字是对被引用网页的描述这个思想被用在WorldWideWebWorm中，主要因为它有助于搜索非文本信息，能够用少量的已下载文档扩大搜索范围。我们大量应用链接描述文字，因为它有助于提高搜索结果的质量。有效地利用链接描述文字技术上存在一些困难，因为必须处理大量的数据。现在我们能抓到24万个网页，已经检索到259万多个链接描述文字。
2.3其它功能
除了PageRank和应用链接描述文字外，Google还有其他几个功能。一,它有所有命中数的位置信息，所以它可以在搜索中广泛应用邻近性。第二，Google跟踪一些可视化外表细节，例如字的字体大小。更大的字的权重要高于其他的。第三，知识库存储了原始的全文html网页。
3.1信息检索
3.2有组织结构的集合与网络的不同点
Web是完全无组织的异构的大量文档的集合。Web中的文档无论内在信息还是隐含信息都存在大量的异构性。例如，文档内部就用了不同的语言(既有人类语言又有程序)，词汇(
首先，我们提供高层次的有关体系结构的讨论。然后，详细描述重要的数据结构。最后，主要应用：抓网页，索引，搜索将会深度探讨。
图1.高层次Google体系结构
4.1Google结构概述
4.2主要数据结构
经过优化的Google数据结构，能够用较小的代价抓取大量文档，建立索引和查询。虽然近几年CPU和输入输出速率迅速提高。磁盘寻道仍然需要10ms。任何时候Google系统的设计都尽可能地避免磁盘寻道。这对数据结构的设计影响很大。
4.2.1大文件
BigFiles是跨越多个文件系统的虚拟文件，用长度是64位的整型数据寻址。多文件系统之间的空间分配是自动完成的。BigFiles包也处理文件描述符的分配。由于操纵系统不能满足我们的需要，BigFiles也支持基本的压缩选项。
4.2.2知识库
知识库包含每个网页的全部HTML。每个网页用zlib(见RFC1950)压缩。压缩技术的选择既要考虑速度又要考虑压缩率。我们选择zlib的速度而不是压缩率很高的bzip。知识库用bzip的压缩率接近4：1。而用zlib的压缩率是3：1。文档一个挨着一个的存储在知识库中，前缀是docID，长度，URL，见图2。访问知识库不需要其它的数据结构。这有助于数据一致性和升级。用其它数据结构重构系统，我们只需要修改知识库和crawler错误列表文件。
4.2.3文档索引
4.2.4辞典
词典有几种不同的形式。和以前系统的重要改进是，词典对内存的要求可以在合理的价格内。当前实现中，一台256M内存的机器就可以把词典装入到内存中。现在的词典包含14万词汇(虽然一些很少用的词汇没有加入到词典中)。它执行分两部分—词汇表(串联在一起，但使用空值隔开)和指针的哈希表的列表的实现。不同的函数词列表有一些辅助的信息，超出了本文以详细解释的范围。
4.2.5点击列表
一个命中列表对应着一个单词在一个文档中出现的位置、字体和大小写信息的列表。命中列表占用了正向索引和反向索引的大部分空间，所以怎样尽可能有效的表示是很重要的。我们考虑了对位置，字体和大小写信息的多种编码方式——简单编码(3个整数)，压缩编码(手工优化分配比特)和霍夫曼编码(Huffmancoding)。命中(hit)的详情见图3。
图3.正、倒排索引和词典
我们的压缩编码每个命中用到两个字节(byte)。有两种命中：特殊命中(fancyhit)和普通命中(plainhit)。特殊命中包括在URL，标题，锚文本和meta标签上的命中。其他的都是普通命中。一个普通的命中包括一个表示大小写的比特(bit)，字体大小，和12个bit表示的单词在文件中的位置(所有比4095大的位置都被标示为4096)。字体在文档中的相对大小用3个比特表示(实际上只用到7个值，因为111标示一个特殊命中)。一个特殊命中包含一个大小写比特，字体大小设置为7用来表示它是一个特殊命中，4个比特用来表示特殊命中的类型，8个比特表示位置。对于锚命中，表示位置的8个比特被分成两部分，4个比特表示在锚文本中的位置，4个比特为锚文本所在docID的哈希(hash)值。由于一个词并没有那么多的锚文本，所以短语搜索受到一些限制。我们期望能更新锚命中的存储方式能让位置和docID哈希值能有更大的范围。我们使用在一个文档中的相对字体大小是因为在搜索时，你并不希望对于内容相同的不同文档，仅仅因为一个文档字体比较大而有更高的评级(rank)。
命中列表的长度存在命中的前面。为了节省空间，命中列表的长度在正向索引中与wordID结合，在反向索引中与docID结合。这样就将长度分别限制在8个比特和5个比特(有一些技巧可以从wordID中借用8个比特)。如果长度超过了这个范围，会在这些比特中使用转义码，在接下来的两个字节(byte)里才存放真正的长度。
4.2.6正向索引
4.2.7反向索引
反向索引与正向索引有着相同的桶，但是它们是先经过排序器处理过的。对每一个合法的wordID，词典包含了一个指向对应的桶的指针。它指向一个docID的列表和相应的命中列表。这个文档列表显示了有这个单词出现的所有文档。
一个重要的事情是如何对这个文档列表排序。一个简单的方法是按照docID排序。在多个单词的查询中，这种方法可以快速地完成两个文档列表的归并。另一种方案是按照这个词在文档中出现的评分(ranking)排序。这种方式使得单个词的查询相当简单，并且多词查询的返回结果也很可能接近开头。但是，归并要困难得多。而且，开发也会困难得多，因为每次评分函数变动就需要重新建立整个索引。我们综合了两种方案，设计了两个倒排桶集合——一个集合只包括标题和锚命中，另一个集合包含所有的命中。这样我们首先检查第一个桶集合，如果没有足够的匹配再检查那个大一点的。
4.3抓取网页
运行网络爬虫是一项很有挑战性的任务。这里不光涉及到巧妙的性能和可靠性问题，更重要的，还有社会问题。抓取是一个很脆弱的应用，因为它需要与成百上千各种各样的web服务器和域名服务器交互，这些都不在系统的控制范围之内。
4.4网站索引
解析——任何被设计来解析整个互联网的解析器都必须处理大量可能的错误。从HTML标签里面的错别字到一个标签里面上千字节的0，非ASCII字符，嵌套了几百层的HTML标签，还有大量超乎人想象的错误和“创意”。为了达到最快的速度，我们没有使用YACC产生CFG(contextfreegramma，上下文无关文法)解析器，而是用flex配合它自己的栈生成了一个词法分析器。开发这样一个解析器需要大量的工作才能保证它的速度和健壮。
为文档建立桶索引——每一个文档解析过后，编码存入桶里面。每一个单词被内存里的哈希表——词典转化成一个wordID。词典哈希表新加的内容都被记录在一个文件里。单词在被转化成我wordID的时候，他们在当前文档中的出现会被翻译成命中列表，并写入正排桶(forwardbarrels)中。建立索引阶段的并行操作主要的困难在于词典需要共享。我们并没有共享整个词典，而是在内存里保存一份基本词典，固定的1千4百万个单词，多余的词写入一个日志文件。这样，多个索引器就可以同时运行，最后由一个索引器来处理这个记录着多余单词的小日志文件。
排序——为了产生倒排索引，排序器取出各个正排的桶，然后根据wordID排序来产生一个标题和锚命中的倒排桶，和一个全文的倒排桶。每次处理一个桶，所以需要的暂存空间很少。而且，我们简单地通过用尽可能多的机器运行多个排序器做到排序的并行化，不同的排序器可以同时处理不同的桶。因为桶并不能全部放在主存里面，排序器会根据wordID和docID将它们进一步分割成可以放在内存里面的桶(basket)。接着，排序器将每个桶载入内存，排好序，把内容写入短的倒排桶和完整的倒排桶。
4.5搜索
搜索的目标是高效地返回高质量的结果。很多大型的商业搜索引擎在效率方面看起来都有很大的进步。所以我们更专注于搜索结果的质量，但是我们相信我们的解决方案只要花一点精力就可以很好的应用到商业的数据上。Google的查询评估流程如图4。
1.解析查询(Query)。
2.把单词转化成wordID。
3.从每个单词的短桶文档列表开始查找。
4.扫描文档列表直到有一个文档匹配了所有的搜索词语。
5.计算这个文档对应于查询的评分。
6.如果我们到达短桶的文档列表结尾，从每个单词的全桶(fullbarrel)文档列表开始查找，跳到第4步。
7.如果我们没有到达任何文档列表的结尾，跳到第4步。
8.根据评分对匹配的文档排序，然后返回评分最高的k个。
图4Google查询评估
4.5.1评分系统
Google比典型的搜索引擎维护了根多的web文档的信息。每一个命中列表(hitlist)包含了位置，字体和大小写信息。而且，我们综合考虑了超链接文本命中和页面的PageRank值。把所有的信息综合成一个评分是很困难的。我们设计了评分函数保证没有一个因素有太大的影响。首先，考虑简单的情况——一个单词的查询。为了对一个单词的查询计算文档的分值，Google首先为这个单词查看这个文档的命中列表。Google将命中分为不同类型(标题，锚，URL，普通文本大字体，普通文本小字体，……)，每一种类型都有自己的类型权重值(type-weight)。类型权重值构成一个由类型寻址(indexed)的向量。Google数出命中列表中每种类型命中的数量。每个数量转化成一个数量权重(count-weight)。数量权重开始随着数量线性增长，但是很快停止增长，以保证单词命中数多于某个数量之后对权重不再有影响。我们通过数量权重向量和类型权重向量的点乘为一个文档算出一个IR分数。最后这个IR分数与PageRank综合产生这个文档最终的评分。
对于一个多词搜索，情况要更复杂。现在，多个命中列表必须一次扫描完，这样一个文档中较近的命中才能比相距较远的命中有更高的评分。多个命中列表里的命中结合起来才能匹配出相邻的命中。对每一个命中的匹配集(matchedset)，会计算出一个接近度。接近度是基于两个命中在文档(或锚文本)中相隔多远计算的，但是被分为10个等级从短语匹配到“一点都不近”。不光要为每一种类型的命中计数，还要为每一种类型和接近度都计数。每一个类型和接近度的组有一个类型-接近度权重(type-prox-weight)。数量被转化成数量权重。我们通过对数量权重和类型-接近度权重做点乘计算出IR分值。所有这些数字和矩阵都会在特殊的调试模式下与搜索结果一起显示出来。这些显示结果在开发评分系统的时候很有帮助
4.5.2反馈
评分函数有很多参数比如类型权重和类型-接近度权重。找出这些参数的权重值简直就跟妖术一样。为了调整这些参数，我们在搜索引擎里有一个用户反馈机制。一个被信任的用户可以选择性地评价所有的返回结果。这个反馈被记录下来。然后在我们改变评分系统的时候，我们能看到修改对之前评价过的搜索结果的影响。尽管这样并不完美，但是这也给我们一些改变评分函数来影响搜索结果的想法。
5.1存储需求
5.2系统性能
5.3搜索性能
Google设计成可伸缩的搜索引擎。主要目标是在快速发展的WorldWideWeb上提供高质量的搜索结果。Google应用了一些技术改进搜索质量包括PageRank，链接描述文字，相邻信
息。进一步说，Google是一个收集网页，建立索引，执行搜索请求的完整的体系结构。
6.1未来的工作
大型Web搜索引擎是个复杂的系统，还有很多事情要做。我们直接的目标是提高搜索效率，覆盖大约100000000个网页。一些简单的改进提高了效率包括请求缓冲区，巧妙地分配
磁盘空间，子索引。另一个需要研究的领域是更新。我们必须有一个巧妙的算法来决定哪些旧网页需要重新抓取，哪些新网页需要被抓取。这个目标已经由实现了。受需求驱动，
用代理cache创建搜索数据库是一个有前途的研究领域。我们计划加一些简单的已经被商业搜索引擎支持的特征，例如布尔算术符号，否定，填充。然而另外一些应用刚刚开始探
的实验证明，通过增加用户主页的权重或书签，PageRank可以个性化。对于链接文本，我们正在试验用链接周围的文本加入到链接文本。Web搜索引擎提供了丰富的研究课题。如
此之多以至于我们不能在此一一列举，因此在不久的将来，我们希望所做的工作不止本节提到的。
6.2高质量搜索
搜索“BillClillton”的结果是theBillClintonJokeoftheDay:April14,1997。Google的设计目标是随着Web的快速发展提供高质量的搜索结果，容易找到信息。为此，
6.3可升级的体系结构
、磁盘容量、网络IO都是瓶颈。在一些操作中，已经改进的Google克服了一些瓶颈。Google的主要数据结构能够有效利用存储空间。进一步，网页爬行，索引，排序已经足够建立大部分web索引，共2千四百万个网页，用时不到一星期。我们希望能在一个月内建立一亿网页的索引。
6.4研究工具
Google不仅是高质量的搜索引擎，它还是研究工具。Google搜集的数据已经用在许多其它论文中，提交给学术会议和许多其它方式。最近的研究，例如，提出了Web查询的局限性
，不需要网络就可以回答。这说明Google不仅是重要的研究工具，而且必不可少，应用广泛。我们希望Google是全世界研究者的资源，带动搜索引擎技术的更新换代。
ScottHassanandAlanSteremberg评价Google的改进。他们的才智无可替代，作者由衷地感谢他们。感谢HectorGarcia-Molina,RajeevMotwani,JeffUllman,andTerryWinograd和全部WebBase开发组的支持和富有深刻见解的讨论。最后感谢IBM，Intel，Sun和投资者的慷慨支持，为我们提供设备。这里所描述的研究是Stanford综合数字图书馆计划的一部分，由国家科学自然基金支持，合作协议号IRI-9411306。DARPA，NASA，Interva研究，Stanford数字图书馆计划的工业合作伙伴也为这项合作协议提供了资金。
引用
RFC1950(zlib)ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html
[Abiteboul97]SergeAbiteboulandVictorVianu,QueriesandComputationontheWeb.ProceedingsoftheInternationalConferenceonDatabaseTheory.Delphi,Greece1997.
[Bagdikian97]BenH.Bagdikian.TheMediaMonopoly.5thEdition.Publisher:Beacon,ISBN:0807061557
[Chakrabarti98]S.Chakrabarti,B.Dom,D.Gibson,J.Kleinberg,P.RaghavanandS.Rajagopalan.AutomaticResourceCompilationbyAnalyzingHyperlinkStructureandAssociatedText.SeventhInternationalWebConference(WWW98).Brisbane,Australia,April14-18,1998.
[Cho98]JunghooCho,HectorGarcia-Molina,LawrencePage.EfficientCrawlingThroughURLOrdering.SeventhInternationalWebConference(WWW98).Brisbane,Australia,April14-18,1998.
[Gravano94]LuisGravano,HectorGarcia-Molina,andA.Tomasic.TheEffectivenessofGlOSSfortheText-DatabaseDiscoveryProblem.Proc.ofthe1994ACMSIGMODInternationalConferenceOnManagementOfData,1994.
[Kleinberg98]JonKleinberg,AuthoritativeSourcesinaHyperlinkedEnvironment,Proc.ACM-SIAMSymposiumonDiscreteAlgorithms,1998.
[Marchiori97]MassimoMarchiori.TheQuestforCorrectInformationontheWeb:HyperSearchEngines.TheSixthInternationalWWWConference(WWW97).SantaClara,USA,April7-11,1997.
[Spertus97]EllenSpertus.ParaSite:MiningStructuralInformationontheWeb.TheSixthInternationalWWWConference(WWW97).SantaClara,USA,April7-11,1997.
[Witten94]IanHWitten,AlistairMoffat,andTimothyC.Bell.ManagingGigabytes:CompressingandIndexingDocumentsandImages.NewYork:VanNostrandReinhold,1994.
[Weiss96]RonWeiss,BienvenidoVelez,MarkA.Sheldon,ChanathipManprempre,PeterSzilagyi,AndrzejDuda,andDavidK.Gifford.HyPursuit:AHierarchicalNetworkSearchEnginethatExploitsContent-LinkHypertextClustering.Proceedingsofthe7thACMConferenceonHypertext.NewYork,1996.
个人简历
LawrencePage生于密歇根州东部的兰辛市并于1995年获得了密歇根大学计算机工程的工学学士学位。他目前是斯坦福大学计算机科学博士候选人。他的一些研究方向包括web链接结构、人机交互、搜索引擎、可扩展性的信息访问接口,个人数据挖掘方法。
9.1Google的可伸缩性
我们把Google设计成具有近期能够处理一亿网页的可伸缩性。我们目前得到了磁盘和机器所需的款额，我们也考虑了大部分数据结构的易扩展性。然而,在100的网页,我们将会非常接近了对各种操作系统的限制，在常见的的操作系统中(现在我们跑在Solaris与Linux)。这些包括诸如可寻址的内存,打开的文件描述符的数目,网络带宽和插座,以及其他许多人。我们相信扩展多到超过一亿万页时将大大增加我们系统的复杂性。
9.2集中索引结构的可伸缩性
计算机性能的提高是它能够以合理的成本对大量文本进行索引，当然，更多的带宽密集型其他媒体，如视频很可能会越来越普遍。
当然，一个分布式的系统比如Gloss或Harvest通常会给索引带来高效和较好的技术解决方案，但由于过高的安装设置和管理成本，似乎难说服全世界都使用这些系统。然而，减少管理成本还是很有大有可能的。如果发生这种情况，并且每个人都开始运行一个分布式的索引系统搜索会当然改善大幅。