20121344018吴乾泰 软件工程1班 计算机与软件学院
The Evolution of the Web and Implications for an Incremental Crawler
Junghoo Cho, Hector Garcia-Molina
Department of Computer Science
Stanford, CA 94305 {cho, hector}@cs.stanford.edu
December 2, 1999
Abstract
In this paper we study how to build an effective incremental crawler. The crawler selectively and incrementally updates its index and/or local collection of web pages, instead of periodically refreshing the collection in batch mode. The incremental crawler can improve the “freshness” of the collection significantly and bring in new pages in a more timely manner. We first present results from an experiment conducted on more than half million web pages over 4 months, to estimate how web pages evolve over time. Based on these experimental results, we compare various design choices for an incremental crawler and discuss their trade-offs. We propose an architecture for the incremental crawler, which combines the best design choices.
1 Introduction
2 Experimental setup
Our initial experiment tries to answer the following questions about the evolving web:
bull; How often does a web page change?
bull; What is the lifespan of a page?
bull; How long does it take for 50% of the web to change?
bull; Can we describe changes of web pages by a mathematical model?
Note that an incremental crawler itself also has to answer some of these questions. For instance, the crawler has to estimate how often a page changes, in order to decide how often to revisit the page. The techniques used for our experiment will shed a light on how an incremental crawler should operate and which statistics-gathering mechanisms it should adopt.
To answer our questions, we crawled around 720,000 pages from 270 sites every day, from February 17th through June 24th, 1999. This was done with the Stanford WebBase crawler, a system designed to create and maintain large web repositories (currently 210GB of HTML is stored). In this section we briefly discuss how the particular sites and pages were selected.
2.1 Monitoring technique
For our experiment, we adopted an active crawling approach with a page window. With active crawling, a crawler visits pages of interest periodically to see if they have changed. This is in contrast to a passive scheme, where say a proxy server tracks the fraction of new pages it sees, driven by the demand of its local users. A passive scheme is less obtrusive, since no additional load is placed on web servers beyond what would naturally be placed. However, we use active crawling because it lets us collect much better statistics, i.e., we can determine what pages to check and how frequently.
The pages to actively crawl are determined as follows. We start with a list of root pages for sites of interest. We periodically revisit these pages, and visit some predetermined number of pages that are reachable, breadth first, from that root. This gives us a window of pages at each site, whose contents may vary from visit to visit. Pages may leave the window if they are deleted or moved deeper within the site. Pages may also enter the window, as they are created or moved closer to the root. Thus, this scheme is superior to one that simply tracks a fixed set of pages, since such a scheme would not capture new pages.
We considered a variation of the page window scheme, where pages that disappeared from the window would still be tracked, if they still exist elsewhere in the site. This scheme could yield slightly better statistics on the lifetime of pages. However, we did not adopt this variation because it forces us to crawl a growing number of pages at each site. As we discuss in more detail below, we very much wanted to bound the load placed on web servers throughout our experiment.
2.2 Site selection
To select the actual sites for our experiment, we used the snapshot of 25 million web pages in our WebBase repository. Based on this snapshot, we identified top 400 “popular” sites as the candidate sites (The definition of the “popular” site is given below.). Then, we contacted the webmasters of all candidate sites to get their permission for our experiment. After this step, 270 sites remained, including sites such as Yahoo (http://yahoo.com), Microsoft (http://microsoft.com), and Stanford (http://www.stanford.edu). Obviously, focusing on the “popular” sites biases our results to a certain degree, but we believe this bias is toward what most people are interested in.
To measure the popularity of a site, we used modified PageRank metric [PB98]. Informally, the PageRank metric considers a page “popular” if it is linked to by many other web pages. More precisely, the PageRank of page P, PR(P), is defined by
PR(P) = d (1 minus; d)[PR(P1)/c1 ... PR(Pn)/cn]
where P1,...,Pn are the pages pointing to P, and c1,...,cn are the number of links going out from pages P1,...,Pn, and d is a damping factor, which was 0.9 in our experiment. This leads to one equation per web page, with an equal number of unknowns. The equations can be solved for the PR values iteratively, starting with all PR values equal to 1. At each step, the new PR(P) value is computed from the old PR(Pi) values (using the equation above), until the values converge. Intuitively, PR(P) value gives us the probability that “random web surfer” is at P at a given time.
剩余内容已隐藏，支付完成后下载完整资料
20121344018吴乾泰 软件工程1班计算机与软件学院
The Evolution of the Web and Implications for an Incremental Crawler
Junghoo Cho, Hector Garcia-Molina
Department of Computer Science
Stanford, CA 94305 {cho, hector}@cs.stanford.edu
December 2, 1999
摘要
在本文中，我们研究如何构建一个有效的增量爬虫。爬虫针对性地增量更新本地索引和文件，而不是周期性地批量更新本地文件。增量抓取爬虫可以显著提高收集的“时效性”，并可以通过更实时的方式获得新的页面。我们首先展现一些试验结果，这些结果来自4个月超过50万网页的数据，去估算网页如何随时间变化。基于这些实验结果，我们比较了增量爬取的不同实现方式，并讨论他们的利弊。我们提出了增量爬行器，它结合了一些最佳的架构设计。
2． 实验设计
我们的初始实验试图回答关于网络变化的下面几个问题：
网页更新的频率是多少？
一个网页的生命周期是多长？
所有网页达到50%的变动率，需要花多长的时间？
我们可以通过描述一个数学模型的网页的变化吗？
3. 试验结果
3.1网页更新的频率是多少？
基于我们收集到的数据，我们可以分析一个网页变动需要多长时间。举个例子，如果一个页面我们监控了50天，在此期间变动了5次，我们可以估算该页面的平均变动时间间隔为50天/ 5 = 10天。需要注意的是估计的变动时间间隔的粒度是一天（24小时），因为我们只能检测每天至多一个变化，即使页面变动的更频繁。此外，如果一个页面一天变动了多次，然后一直没有新的变动，也就是说，一个星期（图1（b）），那么，最后估计的时间间隔可能比真实的结果更长。在这种情况下，我们可以解释我们的估计值是批量变动的频率，这可能比单个变动的平均时间间隔更有意义。
Figure 2: Fraction of pages with given average interval of change
在图2中，我们总结这一分析的结果。在该图中，横轴表示的网页的平均变化的时间间隔，纵轴表示页面变动频率在指定时间间隔内的比例。图2（a）展示了所有域名的统计结果，图2（b）展示了每类域名的统计结果。例如，从图2的第二列，我们可以看出，15%的页面变动周期在一天到一周之间。
从图2（a）的第一列，我们可以看到大量的页面变动频率很高，超过20％的页面每天都在更新。从图2（b）看到，这些经常更新的页面主要来自 .com 域名。.com 域名的页面有超过40％每天都会更新，而其他域名的页面不到10%（图2（b）第一列）。还有一点，edu 和 gov 域名的页面极少变动。这两个域名下的网页超过50％在4个月内都没有更新（图2（b）第5列）。显然，在商业网站的网页，这些网页由专业人员维护，更新很频繁，为了提供及时的信息和吸引更多的用户。
注意，很难估计所有网页的平均更新频率，因为我们实验的时间有限。现在我们知道了一个页面的频率的变化，如果它的更新周期在1天到4个月的话，当网页的更新周期超出这个范围时，我们没法知道这个页面的更新周期。但如果我们假设每天在第一列的页面每天更新一次，第五列的页面每年更新一次（粗略估计），那么，所有网页的更新周期为4个月左右。
总体来看，网页更新的比较频繁，实际的更新频率，不同网页之间差别很大。因此，一个能够有效地跟踪所有这些变化的爬虫会比一个不能跟踪变化的爬虫，提供更好的数据。
3.2 一个网页的生命周期是多久？
在这一小节中，我们关注当新出现了一个网页后，在多长时间内，这个页面都是可以访问的。为了解决这个问题，我们在试验期间统计了每一页的可被访问的时间。也就是说，对于我们抓取到的每一个页面，我们检查了这个页面可以被访问多久（不管页面内容是否更新），这个数字，我们把它定义为页面的lsquo;可见寿命rsquo;。注意，一个页面rsquo;可见寿命lsquo;和它的实际寿命不是完全一样的，因为我们只把网页对我们的监控可见的寿命纳入统计。但我们相信lsquo;可见寿命rsquo;的值是非常接近的网页的实际寿命的。
也就是说，当一个用户从一个特定网页开始搜寻信息，她常常是从根路径开始然后顺着下去访问的。因为用户不能一直地点开链接，所以如果顺着根路径点开一系列链接后，如果还不能找到的话，那么用户就会认为这个网页不存在了。因此，许多用户往往只会从一个页面出发，进入一系列网页，而不是整个页面网络。
我们的实验是在一个有限的时间内进行，所以测量页面的可视寿命其实没有我们刚才描述的那么简单。图3详细地说明了这个问题。对于实验周期内新出现，并且在实验周期内消失的页面，我们可以精确地测量出它的lsquo;可见寿命rsquo;。但是，对于之前就已经存在的页面（如图3（a）和（d）），或在我们的实验结束时（图3的（c）和（d））还为小事的页面，我们无法统计。考虑到这个偏差的存在，我们使用了两种不同的方式预测页面的lsquo;可见周期rsquo;。首先，我们用图3中的长度作为页面的寿命（方法1），其次，我们假定（a）,(c),(d) 中的页面寿命为长度的两倍（方法2 ）。显然，(a),(c),(d) 中的网页寿命可以是他的长度到无限中间的任何一个值，但我们相信2倍是合理的估计。
图4（a）展示了两种方法估计得到的结果。在该图中，横轴表示可见寿命，纵轴显示了给定生命周期的网页的比例。例如，从图4的（a）的第二列，我们可以看到，方法1统计的页面的19％左右有超过一周且小于1个月的生命周期，方法2统计的页面在16％左右。需要注意的是方法1和2在短寿命（第一列，第二列）的网页上，给了我们给了我们相近的结果，但他们对于较长寿命的网页（第三和第四列），结果差异很大。这个结果是因为具有较长寿命的页面常常是在整个试验期间都一直存在的。在图4（b）中，我们可以看到不同域名网页的生命周期。为了避免图表过于混乱，我们只显示了方法1得出的直方图。
有趣的是，我们可以看到，有较长生命周期的网页的比例很特别。所有域名的网页都有70％以上留在我们的监控中一个月以上（图4（a）中，第三和第四列），并且 edu 和 gov 域名的网页有50％以上存活了超过4个月。和预期的一样，com 域名的网页寿命最短，edu 和 org 的网页寿命最长。
3.3 半数的网页更新需要多长的时间？
在前面的小节中，我们主要关注一个个单独的网页随时间变化的情况。例如，我们研究了网页更新，以及网页的生命周期。现在我们稍微改变我们的方向，研究作为一个整体，所有网页如何随时间演变。也就是说，
我们探究 监控中 p％ 的网页都发生了变化需要多长的时间。
为了得到该信息，我们跟踪监控中有多少的网页在一段时间后依然没有更新，结果如图5所示。在该图中，横轴表示从试验开始的天数，纵轴表示在指定的日期，页面还是没有更新的比例。
从图5（a）中，我们可以看到，50%的网页都变化或被换掉需要约50天。从图5（b）中，我们可以确认不同的域名下的页面变动频率差别很大。例如，com 域名的页面达到50%的变动需要11天，而 gov 域名的页面达到相同的变动比例需要4个月。和前面的结果类似，com域名的页面是变化最活跃的，其次是 net，org 域名。edu 和 gov 域名相对静态。同样，我们的结果凸显了对于一个爬虫来说，能够跟踪这些差异性的变化是非常重要的。
3.4 页面的变动可以用数学模型来描述吗？
现在我们来看一下是否可以用数学模型描述网页的变化。首先，我们观察网页变化是否遵循泊松过程。构建网络的变化模式是非常重要的，因为我们可以基于这个模型比较不同的检索策略的效率。
Figure 6: Change intervals of pages
例如，我们想比较不同爬虫的本地数据的即时性，我们需要比较数据中有多少页面是最新的，而如果没有一个准确的网络变化模型的话，这个数字是很难得到的。
泊松过程常常被用来描述一种累计随机事件发生次数的最基本的独立增量过程。举例来说，致命的车祸的发生数，某个服务中心内消费者到达的数量，来自某个区域的电话呼叫数量，等等，通常用一个泊松过程描述。我们相信，对于网页来说，泊松过程是一个非常好的模型，因为很多网页都有我们刚才提到的性质。例如，CNN网站的网页每天变化的数量是基本固定的，但其中单个页面的变化周期是几乎完全随机的，因为页面是否更新取决于与该网页对应的新闻在现实中是如何进展的。
根据泊松过程，我们可以计算两个事件之间的时间间隔。要计算这个间隔，我们先假设第一个事件发生在0时刻，第二个时间发生的时间称为T。然后T的概率密度函数可以由下面的定理[TK98]给出。
我们可以用定理1来验证网络变化是否遵循泊松过程。也就是说，如果一个页面的变动频率遵循率概率为lambda;的泊松过程，那么它的变化的时间间隔分布就是lambda;e－lambda;t。把这个预测和我们的实验数据对比我假设网络上的每个网页都有一个lambda;i的平均变动概率，不同网页的lambda;i不同。然后，我们选择其中平均变化时间间隔是，比如说，10天，然后绘制它们的变化区间的分布。如果页面确实遵循泊松过程，这个图就应该是指数分布的。在图6中，我们显示了一些这样的图。图6（a）是变化间隔为10天的页面的图表中，图6（b）是20天的。
横轴表示变化的时间间隔，纵轴表示指定时间间隔的比例。在图中，纵轴是对数显示的，以凸显该分布是指数的。尽管存在小的变化，我们可以清楚地看到这是一个泊松过程。
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[28791]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
课题毕业论文、外文翻译、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
