1. Introduction

A crawler is a program that retrieves Web pages, commonly for use by a search engine [Pinkerton 1994]
or a Web cache. Roughly, a crawler starts off with the URL for an initial page P0. It retrieves P0,
extracts any URLs in it, and adds them to a queue of URLs to be scanned. Then the crawler gets URLs
from the queue (in some order), and repeats the process. Every page that is scanned is given to a client
that saves the pages, creates an index for the pages, or summarizes or analyzes the content of the pages.

Crawlers are widely used today. Crawlers for the major search engines (e.g., Altavista [1], InfoSeek [2],
Excite [3], and Lycos [4]) attempt to visit most text Web pages, in order to build content indexes. Other
crawlers may also visit many pages, but may look only for certain types of information (e.g., email
addresses). At the other end of the spectrum, we have personal crawlers that scan for pages of interest to
a particular user, in order to build a fast access cache (e.g. NetAttche [5], WebSnake [6]).

The design of a good crawler presents many challenges. Externally, the crawler must avoid overloading
Web sites or network links as it goes about its business [Koster 1995]. Internally, the crawler must deal
with huge volumes of data. Unless it has unlimited computing resources and unlimited time, it must
carefully decide what URLs to scan and in what order. The crawler must also decide how frequently to
revisit pages it has already seen, in order to keep its client informed of changes on the Web. Inspite of all
these challenges, and the importance of crawlers on the Internet, very little research has been done on
crawlers.

In this paper we address one of these important challenges: How should a crawler select URLs to scan
from its queue of known URLs? If a crawler intends to perform a single scan of the entire Web, and the
load placed on target sites is not an issue, then any URL order will suffice. That is, eventually every
single known URL will be visited, so the order is not critical. However, most crawlers will not be able to
visit every possible page for two main reasons:

Their client may have limited storage capacity, and may be unable to index or analyze all pages.
Currently the Web contains about 1.5TB and is growing rapidly, so it is reasonable to expect that

most clients will not want or will not be able to cope with all that data [Kahle 1997] .
Crawling takes time, so at some point the crawler may need to start revisiting previously scanned
pages, to check for changes. This means that it may never get to some pages. It is currently
estimated that over 600GB of the Web changes every month [Kahle 1997].

In either case, it is important for the crawler to visit "important" pages first, so that the fraction of the
Web that is visited (and kept up to date) is more meaningful. In this paper we present several useful
definitions of importance, and develop crawling priorities so that important pages have a higher
probability of being visited first. We also present experimental results from crawling the Stanford
University Web pages that show how effective the different crawling strategies are.

Of course, a crawler must also avoid overloading target sites, especially if they contain many important
pages. In this paper we do not address this issue. That is, we assume that URLs selected for scanning
may be delayed by a crawler component that monitors site loads, but we do not study here how this
delay component works. Similarly, we do not consider in this paper rescanning pages. To simplify our
evaluations, we assume that a crawler does not start revisiting pages until it has finished visiting pages.
In practice one may of course wish to start rescanning important pages even before a crawl is completed,
but this is beyond the scope of this paper.