The Anatomy of a Large-Scale Hypertextual Web Search Engine
Abstract：In this paper, we present Google, a prototype of a large-scale search engine which makes heavy use of the structure present in hypertext. Google is designed to crawl and index the Web efficiently and produce much more satisfying search results than existing systems. The prototype with a full text and hyperlink database of at least 24 million pages is available at http://google.stanford.edu/
To engineer a search engine is a challenging task. Search engines index tens to hundreds of millions of web pages involving a comparable number of distinct terms. They answer tens of millions of queries every day. Despite the importance of large-scale search engines on the web, very little academic research has been done on them. Furthermore, due to rapid advance in technology and web proliferation, creating a web search engine today is very different from three years ago. This paper provides an in-depth description of our large-scale web search engine -- the first such detailed public description we know of to date.
Apart from the problems of scaling traditional search techniques to data of this magnitude, there are new technical challenges involved with using the additional information present in hypertext to produce better search results. This paper addresses this question of how to build a practical large-scale system which can exploit the additional information present in hypertext. Also we look at the problem of how to effectively deal with uncontrolled hypertext collections where anyone can publish anything they want.
Keywords: World Wide Web, Search Engines, Information Retrieval, PageRank, Google
1. Introduction
The web creates new challenges for information retrieval. The amount of information on the web is growing rapidly, as well as the number of new users inexperienced in the art of web research. People are likely to surf the web using its link graph, often starting with high quality human maintained indices such as Yahoo! or with search engines. Human maintained lists cover popular topics effectively but are subjective, expensive to build and maintain, slow to improve, and cannot cover all esoteric topics. Automated search engines that rely on keyword matching usually return too many low quality matches. To make matters worse, some advertisers attempt to gain peoples attention by taking measures meant to mislead automated search engines. We have built a large-scale search engine which addresses many of the problems of existing systems. It makes especially heavy use of the additional structure present in hypertext to provide much higher quality search results. We chose our system name, Google, because it is a common spelling of googol, or 10100 and fits well with our goal of building very large-scale search engines.
1.1 Web Search Engines -- Scaling Up: 1994 - 2000
Search engine technology has had to scale dramatically to keep up with the growth of the web. In 1994, one of the first web search engines, the World Wide Web Worm (WWWW) [McBryan 94] had an index of 110,000 web pages and web accessible documents. As of November, 1997, the top search engines claim to index from 2 million (WebCrawler) to 100 million web documents (from Search Engine Watch). It is foreseeable that by the year 2000, a comprehensive index of the Web will contain over a billion documents. At the same time, the number of queries search engines handle has grown incredibly too. In March and April 1994, the World Wide Web Worm received an average of about 1500 queries per day. In November 1997, Altavista claimed it handled roughly 20 million queries per day. With the increasing number of users on the web, and automated systems which query search engines, it is likely that top search engines will handle hundreds of millions of queries per day by the year 2000. The goal of our system is to address many of the problems, both in quality and scalability, introduced by scaling search engine technology to such extraordinary numbers.
1.2. Google: Scaling with the Web
Creating a search engine which scales even to todays web presents many challenges. Fast crawling technology is needed to gather the web documents and keep them up to date. Storage space must be used efficiently to store indices and, optionally, the documents themselves. The indexing system must process hundreds of gigabytes of data efficiently. Queries must be handled quickly, at a rate of hundreds to thousands per second.
These tasks are becoming increasingly difficult as the Web grows. However, hardware performance and cost have improved dramatically to partially offset the difficulty. There are, however, several notable exceptions to this progress such as disk seek time and operating system robustness. In designing Google, we have considered both the rate of growth of the Web and technological changes. Google is designed to scale well to extremely large data sets. It makes efficient use of storage space to store the index. Its data structures are optimized for fast and efficient access (see section 4.2). Further, we expect that the cost to index and store text or HTML will eventually decline relative to the amount that will be available. This will result in favorable scaling properties for centralized systems like Google.
1.3 Design Goals
1.3.1 Improved Search Quality
Our main goal is to improve the quality of web search engines. In 1994, some people believed that a complete se
剩余内容已隐藏，支付完成后下载完整资料
大型超文本网络搜索引擎的剖析
摘要：在本文中，我们介绍谷歌---大型搜索引擎的原型，它使得大量使用的结构以文本的形式存在，谷歌的目的比现有系统检索和索引的Web效率更高并产生更满意的搜索结果。原型的全文和超链接的数据库，至少有24万页，可从以下地址获得http://google.stanford.edu/。
开发搜索引擎是一个具有挑战性的任务。搜索引擎索引有数以百万计的网页涉及相当数量的独特条件。它们每一天回答数以千万计的查询，尽管大型搜索引擎在网络上很重要，但在这上面做的学术研究还很少，此外，由于快速的科技进步和网络的扩散，创造一个网络搜索引擎今天和三年前是非常不同的。本文进行了深入论述我们的大型网络搜索引擎---这是我们到目前为止知道的首次如此详细的公开论述。
对这种规模的数据来说，除了扩大传统的搜索技术的问题外，有了新的技术挑战，使用补充资料中存在的超文本，可以产生更好的搜索结果。本文论述了这一问题，即如何建立一个实用的大型系统，可利用补充资料中存在的超文本。另外我们看一下的问题是如何有效地处理不受控制的超文本集合在那里任何人都可以发表任何他们想要的。
关键字：万维网，搜索引擎，信息检索，PageRank, Google
1. 简介
Web 给信息检索带来了新的挑战。Web上的信息量快速增长，同时不断有毫无经验的新用户来体验Web这门艺术。人们常常使用超级链接在网上冲浪，通常都以象 Yahoo这样重要的网页或搜索引擎开始。大家认为List(目录)有效地包含了大家感兴趣的主题，但是它具有主观性，建立和维护的代价高，升级慢，不能包括所有深奥的主题。基于关键词的自动搜索引擎通常返回太多的低质量的匹配。使问题更遭的是，一些广告为了赢得人们的关注想方设法误导自动搜索引擎。我们建立了一个大型搜索引擎解决了现有系统中的很多问题。应用超文本结构，大大提高了查询质量。我们的系统命名为google，取名自googol的通俗拼法，即10的100次方，这和我们的目标建立一个大型搜索引擎不谋而合。
1.1网络搜索引擎的升级换代： 1994年至2000年
随着网络的发展，网络搜索引擎技术不得不升级换代。1994年，第一个网络搜索引擎，万维网蠕虫（ WWWW ） [ McBryan 94 ]，它有十一万的索引网页和网络可访问的文件。截至1997年11月，最热门搜索引擎的网页文件要求索引从200万（ 网络爬虫 ）至1亿（来自Search Engine Watch)） 。可以预见，到2000年，一个全面的索引的网页将包含超过10亿文件。与此同时，一些搜索引擎的查询处理增加的也难以置信了。1994年3月和4月，万维网蠕虫平均每天接到约1500个查询。1997年11月，Altavista声称每天处理的查询约为2000万，随着越来越多的用户在网络上出现，以及查询搜索引擎的自动化系统的增加，到2000年。最热门搜索引擎可能每天将处理数以亿计的查询。我们系统的设计目标要解决许多问题，包括质量和可升级性，引入升级搜索引擎技术，把它升级到如此大量的数据上。
1.2 Google：跟 上 Web的步伐
建立一个能够和当今web规模相适应的搜索引擎会面临许多挑战，快速检索技术是需要收集网页文件，并使他们及时更新。存储空间必须有效地利用存储指数和可选的文件本身。索引系统必须有效处理百千兆字节的数据。查询必须迅速处理，速度在数百至数千每秒。
这些任务正变得越来越困难，因为网页在变化和发展中。然而，硬件的性能和成本已大大改善，以部分抵消了困难。然而，这方面的进展有几个明显的例外，如磁盘寻道时间和作业系统的鲁莽性。在设计谷歌时我们既考虑了网络的发展又考虑了技术的变化。谷歌被设计的与庞大的数据集相称的很好。它有效地利用存储空间来存储索引。它的数据结构优化，以快速，高效的访问。此外，我们期望的费用指数和存储文本或HTML最终下降到相对将是可利用的数额。这将导致结构性能良好的集中系统，如谷歌。
1.3 设计目标
1.3.1提高搜索质量
我们的主要目标是提高网页搜索引擎的搜索质量，在1994年，有些人认为一个完备的搜索索引就可以很容易找到任何东西。根据Best of the Web 1994 -- Navigators网站说，“最好的导航服务就是（输入一次）能够很容易地在这个网站中找到任何东西。”但是，到了1997年的网站，情况就大不相同了。任何一个使用过搜索引擎的人都可以证明：完备的搜索索引并不是影响搜索结果的唯一因素。'Junk results'经常因为一个用户感兴趣的结果而筋疲力尽。事实上，直到1997年11月以前，在最好的四个商业搜索引擎中，仅仅只有一个能够找到自己（在排在顶端的10个结果中，能根据它的名字返回自己的搜索页面）。其中一个主要的原因是（搜索结果）文件的数目以很多数量级的速度增长，但是用户阅读文件的能力却没有随着增长。人们任然不愿意查看前面的几十条搜索结果。就是这个原因，随着收集数量的增长，我们需要高准确度的工具（能在前几十个结果中把一些相关的返回资料表达出来）。更确切地，我们认为的“相关”概念仅仅指那些最适合的文件，因为这里或许有成百上千的微小相关的文件。这个高准确度是非常重要的，甚至达到系统重新返回所有与这相关的文件的代价。最近，值得乐观的是超文本的使用能帮助提高搜索和其他应用[Marchiori 97] [Spertus 97] [Weiss 96] [Kleinberg 98]。特别地，链接结构[Page 98]和链接文本为相关的判断和过滤的能力提供了很多有用的信息。Google就是利用了链接结构和锚文本。
1.3.2 学术型搜索引擎调查
撇开（网站的）飞速增长不谈，随着时间的流逝，网站也不断地变得商业化了。在1993年，只有1.5%的网站服务器是属于.com域名的，到了1997年，这些网站的比例就超过了60%了。在此同时，搜索引擎也开始从专科院校转移到商业领域。到现在为止，大部分搜索引擎是依靠很少公开技术细节的公司发展下去的。这引起搜索引擎技术任然是一个巨大的空白技术，而且成为广告的起源了，我们有一个强烈的目标就是推动更多的技术开发和理解往学术领域发展。
2 系统剖析
|
Figure 1. High Level Google Architecture |
这一节，我们将看看整个系统是如何工作，见图1。为了效率大部分Google是用c或c 实现的，既可以在Solaris也可以在Linux上运行。
Google 系统中，抓网页（下载网页）是由几个分布式crawlers完成的。一个URL服务器负责向crawlers提供URL列表。抓来的网页交给存储服务器 r。然后，由存储服务器压缩网页并把它们存到知识库中。每个网页都有一个ID，称作docID，当新URL从网 页中分析出时，就被分配一个docID。由索引器和排序器负责建立索引。索引器从知识库中读取文档，对其解压缩和分析。每个文档被转换成一组词的出现情况，称作命中hits。Hits 纪录了词，词在文档中的位置，最接近的字号，大小写。索引器把这些hits分配到一组桶barrel中，产生经过部分排序后的索引。索引器的另一个重要功能是分析网页中所有的链接，将有关的重要信息存在链接描述anchors文件中。该文件包含了足够的信息，可以用来判断每个链接链出链入节点的信息，和链 接文本。 URL分解器resolver阅读链接描述anchors文件，并把相对URL转换成绝对URL，再转换成docID。为链接描述文本编制索引，并与它所 指向的docID关联起来。同时建立由docID对组成的链接数据库。用于计算所有文档的PageRank值。用docID分类后的barrels，送给 排序器sorter，再根据wordID进行分类，建立反向索引inverted index。这个操作要恰到好处，以便几乎不需要暂存空间。排序器还给出docID和偏移量列表，建立反向索引。一个叫DumpLexicon的程序把这 个列表和由索引器产生的字典结合在一起，建立一个新的字典，供搜索器使用。这个搜索器就是利用一个Web服务器，使用由DumpLexicon所生成的字典，利用上述反向索引以及页面等级PageRank来回答用户的提问。
3 结论
Google设计成可伸缩的搜索引擎。主要目标是在快速发展的World Wide Web上提供高质量的搜索结果。Google应用了一些技术改进搜索质量包括PageRank，链接描述文字，相邻信息。进一步说，Google是一个收集网页，建立索引，执行搜索请求的完整的体系结构。
3.1 未来的工作
大型Web搜索引擎是个复杂的系统，还有很多事情要做。我们直接的目标是提高搜索效率，覆盖大约100000000个网页。一些简单的改进提高了效率包括请 求缓冲区，巧妙地分配磁盘空间，子索引。另一个需要研究的领域是更新。我们必须有一个巧妙的算法来决定哪些旧网页需要重新抓取，哪些新网页需要被抓取。这 个目标已经由实现了。受需求驱动，用代理cache创建搜索数据库是一个有前途的研究领域。我们计划加一些简单的已经被商业搜索引擎支持的特征，例如布尔 算术符号，否定，填充。然而另外一些应用刚刚开始探索，例如相关反馈，聚类（Google现在支持简单的基于主机名的聚类）。我们还计划支持用户上下文 （象用户地址），结果摘要。我们正在扩大链接结构和链接文本的应用。简单的实验证明，通过增加用户主页的权重或书签，PageRank可以个性化。对于链 接文本，我们正在试验用链接周围的文本加入到链接文本。Web搜索引擎提供了丰富的研究课题。如此之多以至于我们不能在此一一列举，因此在不久的将来，我们希望所做的工作不止本节提到的。
3.2 高质量搜索
当 今Web搜索引擎用户所面临的最大问题是搜索结果的质量。结果常常是好笑的，并且超出用户的眼界，他们常常灰心丧气浪费了宝贵的时间。例如，一个最流行的 商业搜索引擎搜索“Bill Clillton”的结果是the Bill Clinton Joke of the Day: April 14, 1997。Google的设计目标是随着Web的快速发展提供高质量的搜索结果，容易找到信息。为此，Google大量应用超文本信息包括链接结构和链接 文本。Google还用到了相邻性和字号信息。评价搜索引擎是困难的，我们主观地发现Google的搜索质量比当今商业搜索引擎高。通过PageRank分析链接结构使Google能够评价网页的质量。用链接文本描述链接所指向的网页有助于搜索引擎返回相关的结果（某种程度上提高了质量）。最后，利用相邻性信息大大提高了很多搜索的相关性。
3.3可升级的体系结构
除了搜索质量，Google设计成可升级的。空间和时间必须高效，处理整个Web时固定的几个因素非常重要。实现Google系统，CPU、访存、内存容 量、磁盘寻道时间、磁盘吞吐量、磁盘容量、网络IO都是瓶颈。在一些操作中，已经改进的Google克服了一些瓶颈。Google的主要数据结构能够有效 利用存储空间。进一步，网页爬行，索引，排序已经足够建立大部分web索引，共24000000个网页，用时不到一星期。我们希望能在一个月内建立 100000000网页的索引。
3.4 研究工具
Google 不仅是高质量的搜索引擎，它还是研究工具。Google搜集的数据已经用在许多其它论文中，提交给学术会议和许多其它方式。最近的研究，例如，提出
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[500244]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
