8. Conclusion

In this paper we addressed the problem of ordering URLs for crawling. We listed different kinds of

importance metrics, and built three models to evaluate crawlers. We experimentally evaluated several
combinations of importance and ordering metrics, using the Stanford Web pages.

In general our results show that PageRank, IR’(P), is an excellent ordering metric when either pages
with many backlinks or with high PageRank are sought. In addition, if the similarity to a driving query is
important, then it is also useful to visit earlier URLs that:

Have anchor text that is similar to the driving query;
Have some of the query terms within the URL itself; or
Have a short link distance to a page that is known to be hot.

With a good ordering strategy, it seems to be possible to build crawlers that can rather quickly obtain a
significant portion of the hot pages. This can be extremely useful when we are trying to crawl large
portions of the Web, when are resources are limited, or when we need to revisit pages often to detect
changes.

6. Similarity-Based Crawlers

In the experiments of Section 6, we compared three different backlink-based crawlers. In this section,
we present the results of our experiments on similarity-based crawlers. The similarity-based importance
metric, IS(P), measures the relevance of each page to a topic or a query that the user has in mind. There
are clearly many possible IS(P) metrics to consider, so our experiments here are not intended to be
comprehensive. Instead, our goal is to briefly explore the potential of various ordering schemes in some
sample scenarios. In particular, for our first three experiments we consider the following IS(P)
definition: A page is considered hot if it contains the word computer in its title or if it has more th an 10
occurrences of computer in its body. In our fourth experiment we consider a different definition.

Crawling algorithm (similarity-based)

Function description

enqueue(url_queue, starting_url);
while (not empty(hot_queue) and not empty(url_queue)) {
url = dequeue2(hot_queue, url_queue);
page = crawl_page(url);
enqueue(crawled_pages, (url, page));
url_list = extract_urls(page);
for each u in url_list
enqueue(links, (url, u));
if [u not in url_queue] and
[u not in hot_queue] and
[(u,-) not in crawled_pages]
if [u contains computer in anchor or url]
enqueue(hot_queue, u);
else
enqueue(url_queue, u);
reorder_queue(url_queue);
reorder_queue(hot_queue);
}

dequeue2(queue1, queue2) :
if (not empty(queue1)) dequeue(queue1);
else
dequeue(queue2);

For similarity-based crawling, the crawler of Figure 1 is not appropriate, since it does not take the
content of the page into account. To give priority to the pages mentioning computer, we modified our
crawler as shown in Figure 4. This crawler keeps two queues of URLs to visit: hot_queue stores the
URLs that have been seen in an anchor mentioning the word computer, or that have the word computer
within them. The second queue, url_queue, keeps the rest of the URLs. The crawler first takes URL to
visit from hot_queue.

The observed unexpected performance difference arises from the breadth-first crawler’s FIFO nature.
The breadth-first crawler fetches the pages in the order they are found. If a computer-related page is
crawled earlier, then the crawler discovers and visits its child pages earlier as well. These pages have a
tendency to also be computer related, so performance is better.

Thus, the observed property is that if a page has a high IS(P) value, then its children are likely to have a
higher IS(P) value too. To take advantage of this property, we modified our crawler as shown in Figure
5. This crawler places in the hot_queue URLs that have the target keyword in their anchor or within, or
that are within 3 links from a hot page.

Crawling algorithm (modified similarity-based)

enqueue(url_queue, starting_url);
while (not empty(hot_queue) and not empty(url_queue)) {
url = dequeue2(hot_queue, url_queue);
page = crawl_page(url);
if [page contains 10 or more computer in body
or one computer in title]
hot[url] = TRUE;
enqueue(crawled_pages, (url, page));
url_list = extract_urls(page);
for each u in url_list
enqueue(links, (url, u));
if [u not in url_queue] and
[u not in hot_queue] and
[(u,-) not in crawled_pages]
if [u contains computer in anchor or url]
enqueue(hot_queue, u);
else if [distance_from_hotpage(u) < 3]
enqueue(hot_queue, u);
else
enqueue(url_queue, u);
reorder_queue(url_queue);
reorder_queue(hot_queue);
}

Function description

distance_from_hotpage(u) :
return 0 if [hot[u] = TRUE];
return 1 if [hot[v] = TRUE] and [(v, u) in links]
for some v;
return 2 if [hot[v] = TRUE] and
[(v, w) in links] and [(w, u) in links]
some v, w;

5. Experimental Setup

To avoid network congestion and heavy loads on the servers, we did our experimental evaluation in two
steps. In the first step, we physically crawled all Stanford Web pages and built a local repository of the
pages. This was done with the Stanford WebBase, a system designed to create and maintain large web
repositories. It is capable of high indexing speeds (about 50 pages per second), and large data
repositories (currently 150GB of HTML is stored).

After we built the repository, we ran our virtual crawlers on it to evaluate the different crawling
schemes. Note that even though we had the complete image of the Stanford domain in the repository,
our virtual crawler based its crawling decisions only on the pages it saw for itself. In this section we
briefly discuss how the WebBase crawler operates, and how the particular database was obtained for our
experiments.

5.1 WebBase Crawler

WebBase runs several processes at a time, which crawl web pages. These processes receive a list of
URLs to be downloaded and simply return the full content of the HTML or any errors which happened
trying to get the pages. The crawling processes open several hundred connections at a time, resulting in
a crawling speed of about 25 pages/second for each process. Since servers can only handle a few tens of
hits per second at most, and slowing down servers with a web crawler is a problem, we use two different
kinds of load balancing in our system. First, our system splits all URLs which are going to be crawled
into 500 queues based on a hash of their server name. This causes all URLs from a given server to go
into the same queue. The crawlers then read one URL from each queue at a time, moving to a new queue
for each URL. This makes sure a given server is hit only once for every 500 URLs that are crawled.
Also, for servers that are slow at returning documents, only one connection is allowed from the crawler
to a particular server at a time. As is mentioned in Section 1, these kinds of load balancing requirements
affect the freedom a crawler has in deciding the crawl order.

The actual data the system is allowed to get is reduced for two reasons. The first is that many heuristics
are needed to avoid automatically generated, and potentially infinite, sets of pages. For example, any
URLs containing "/cgi-bin/" are not crawled, because they are likely to contain programs which generate
infinite sets of pages, or producing other undesirable side effects such as an unintended vote in an online
election. Several other heuristics based on the Location Metric described above are used to weed out
URLs which look undesirable. Another way the data set is reduced is through the robots exclusion
protocol[7], which allows webmasters to define pages they do not want crawled by automatic systems.

5.2 Description of Dataset

To download an image of the Stanford web pages, we started WebBase with an initial list of
"stanford.edu" URLs. These 89,119 URLs were obtained from an earlier crawl. During the crawl,
non-Stanford URLs were ignored. At the end of the process, we had 784,592 known URLs to Stanford
pages. It should be noted that 352,944 of the known URLs were on one server, www.slac.stanford.edu
[8], which has a program that generates infinite numbers of web pages. The crawl was stopped before it
was complete, but most of the uncrawled URLs were on only a few servers so we believe the dataset we
used to be a reasonable representation of the stanford.edu web. This dataset consisted of about 225,000
crawled valid HTML pages using roughly 2.5 GB of space for the raw pages.

We should stress that the virtual crawlers that will be discussed next do not use WebBase directly. As

stated earlier, they use the dataset collected by the WebBase crawler, and do their own crawling on it.
The virtual crawlers are simpler than the Web Base crawler. For instance, they can detect if a URL is
invalid simply by seeing if it is in the dataset. Similarly, they do not need to distribute the load to visited
sites. These simplifications are fine, since the virtual crawlers are only used to evaluate ordering
schemes, and not to do real crawling.

4. Ordering Metrics

A crawler keeps a queue of URLs it has seen during the crawl, and must select from this queue the next
URL to visit. The ordering metric O is used by the crawler for this selection, i.e., it selects the URL u
such that O(u) has the highest value among all URLs in the queue. The O metric can only use
information seen (and remembered if space is limited) by the crawler.

The O metric should be designed with an importance metric in mind. For instance, if we are searching
for high IB(P) pages, it makes sense to use an O(u) = IB’(P), where P is the page u points to. However,
it might also make sense to consider an O(u) = IR’(P), even if our importance metric is not weighted. In
our experiments, we explore the types of ordering metrics that are best suited for either IB(P) or IR(P).

For a location IL(P) importance metric, we can use that metric directly for ordering since the URL of P
directly gives the IL(P) value. However, for forward link IF(P) and similarity IS(P) metrics, it is much
harder to devise an ordering metric since we have not seen P yet. As we will see, for similarity, we may
be able to use the text that anchors the URL u as a predictor of the text that P might contain. Thus, one
possible ordering metric O(u) is IS(A, Q), where A is the anchor text of the URL u, and Q is the driving
query.

3. Problem Definition

Our goal is to design a crawler that if possible visits high I(P) pages before lower ranked ones, for some
definition of I(P). Of course, the crawler will only have available I’(P) values, so based on these it will
have to guess what are the high I(P) pages to fetch next.

Our general goal can be stated more precisely in three ways, depending on how we expect the crawler to
operate. (In our evaluations of Sections 6 and 7 we use the second model in most cases, but we do
compare it against the first model in one experiment. Nevertheless, we believe it is useful to discuss all
three models to understand the options.)

Crawl & Stop. Under this model, the crawler C starts at its initial page P0 and stops after visiting K
pages. At this point a perfect crawler would have visited pages R1, ..., RK , where R1 is the page with the

highest importance value, R2 is the next highest, and so on. We call pages R1 through RK the hot pages.
The K pages visited by our real crawler will contain only M pages with rank higher than or equal to
I(RK ). We define the performance of the crawler C to be PCS(C) = (M•100)/K. The performance of the
ideal crawler is of course 100%. A crawler that somehow manages to visit pages entirely at random, and
may revisit pages, would have a performance of (K•100)/T, where T is the total number of pages in the
Web. (Each page visited is a hot page with probability K/T. Thus, the expected number of desired pages
when the crawler stops is K 2 /T.)

Crawl & Stop with Threshold. We again assume that the crawler visits K pages. However, we are now
given an importance target G, and any page with I(P) >= G is considered hot. Let us assume that the
total number of hot pages is H. The performance of the crawler, PST (C), is the percentage of the H hot
pages that have been visited when the crawler stops. If K < H , then an ideal crawler will have
performance (K•100)/H. If K >= H, then the ideal crawler has 100% performance. A purely random
crawler that revisits pages is expected to visit (H/T) •K hot pages when it stops. Thus, its performance is
(K•100)/T. Only if the random crawler visits all T pages, is its performance expected to be 100%.

Limited Buffer Crawl. In this model we consider the impact of limited storage on the crawling process.
We assume that the crawler can only keep B pages in its buffer. Thus, after the buffer fills up, the
crawler must decide what pages to flush to make room for new pages. An ideal crawler could simply
drop the pages with lowest I(P) value, but a real crawler must guess which of the pages in its buffer will
eventually have low I(P) values. We allow the crawler to visit a total of T pages, equal to the total
number of Web pages. At the end of this process, the percentage of the B buffer pages that are hot gives
us the performance PBC(C). We can define hot pages to be those with I(P) >= G, where G is a target

importance, or those with I(P) >= I(RB), where RB is the page with the Bth highest importance value.
The performances of an ideal and a random crawler are analogous to those in the previous cases.

Note that to evaluate a crawler under any of these metrics, we need to compute the actual I(P) values of
pages, and this involves crawling the "entire" Web. To keep our experiments (Section 6 and 7)
manageable, we define the entire Web to be the Stanford University pages, and we only evaluate
performance in this context. That is, we assume that all pages outside Stanford have I(P) = 0, and that
links to pages outside Stanford or from pages outside Stanford do not count in I(P ) computations. In
Section 6.4 we study the implications of this assumption by also analyzing a smaller Web within the
Stanford domain, and seeing how Web size impacts performance.

2. Importance Metrics

Not all pages are of equal interest to the crawler’s client. For instance, if the client is building a
specialized database on a particular topic, then pages that refer to that topic are more important, and
should be visited as early as poss ible. Similarly, a search engine may use the number of Web URLs that
point to a page, the so-called backlink count, to rank user query results. If the crawler cannot visit all
pages, then it is better to visit those with a high backlink count, since this will give the end-user higher
ranking results.

Given a Web page P, we can define the importance of the page, I(P), in one of the following ways
(These metrics can be combined, as will be discussed later.):

1. Similarity to a Driving Query Q. A query Q drives the crawling process, and I(P) is defined to be
the textual similarity between P and Q. Similarity has been well studied in the Information
Retrieval (IR) community [Salton 1989] and has been applied to WWW environment [Yuwono
1995]. We use IS(P) to refer to the importance metric in this case. We also use IS(P, Q) when we
wish to make the query explicit.

To compute similarities, we can view each document (P or Q) as an m-dimensional vector <w1, ...,

wn>. The term wi in this vector represents the ith word in the vocabulary. If wi does not appear in
the document, then wi is zero. If it does appear, wi is set to represent the significance of the word.

One common way to compute the significance wi is to multiply the number of times the ith word

appears in the document by the inverse document frequency (idf ) of the ith word. The idf factor is
one divided by the number of times the word appears in the entire "collection," which in this case
would be the entire Web. The idf factor corresponds to the content discriminating power of a
word: a term that appears rarely in documents (e.g., "queue") has a high idf , while a term that
occurs in many documents (e.g., "the") has a low idf . (The w terms can also take into account

occurs in many documents (e.g., the ) has a low df . (The wi terms can also take into account
where in a page the word appears. For instance, words appearing in the title of an HTML page
may be given a higher weight than other words in the body.) The similarity between P and Q can
then be defined as the inner product of the P and Q vectors. Another option is to use the cosine
similarity measure, which is the inner product of the normalized vectors.

Note that if we do not use idf terms in our similarity computation, the importance of a page, IS(P),
can be computed with "local" information, i.e., P and Q. However, if we use idf terms, then we
need global information. During the crawling process we have not seen the entire collection, so we
have to estimate the idf factors from the pages that have been crawled, or from some reference idf
terms computed at some other time. We use IS’(P) to refer to the estimated importance of page P,
which is different from the actual importance IS(P), which can be computed only after the entire
Web has been crawled. If idf factors are not used, then IS’(P) = IS(P).

2. Backlink Count. The value of I(P) is the number of links to P that appear over the entire Web. We
use IB(P) to refer to this importance metric. Intuitively, a page P that is linked to by many pages is
more important than one that is seldom referenced. This type of "citation count" has been used
extensively to evaluate the impact of published papers. On the Web, IB(P) is useful for ranking
query results, giving end-users pages that are more likely to be of general interest.

Note that evaluating IB(P) requires counting backlinks over the entire Web. A crawler may
estimate this value with IB’(P), the number of links to P that have been seen so far.

3. PageRank. The IB(P) metric treats all links equally. Thus, a link from the Yahoo home page
counts the same as a link from some individual’s home page. However, since the Yahoo home
page is more important (it has a much higher IB count), it would make sense to value that link
more highly. The PageRank backlink metric, IR(P), recursively defines the importance of a page
to be the weighted sum of the backlinks to it. Such a metric has been found to be very useful in
ranking results of user queries [Page 1998.2]. We use IR’(P) for the estimated value of IR(P) when
we have only a subset of pages available.

More formally, if a page has no outgoing link, we assume that it has outgoing links to every single
Web page. Next, consider a page P that is pointed at by pages T 1, ..., T n. Let ci be the number of
links going out of page T i. Also, let d be a damping factor (whose intuition is given below). Then,
the weighted backlink count of page P is given by

IR(P) = (1-d) + d ( IR(T 1)/c1 + ... + IR(T n)/cn)

This leads to one equation per Web page, with an equal number of unknowns. The equations can
be solved for the IR values. They can be solved iteratively, starting with all IR values equal to 1.
At each step, the new IR(P) value is computed from the old IR(T i) values (using the equation
above), until the values converge. This calculation corresponds to computing the principal
eigenvector of the link matrices. PageRank is described in much greater detail in [Page 1998.2].

One intuitive model for PageRank is that we can think of a user "surfing" the Web, starting from
any page, and randomly selecting from that page a link to follow. When the user reaches a page
with no outlinks, he jumps to a random page. Also, when the user is on a page, there is some

probability, d, that the next visited page will be completely random. This damping factor d makes
sense because users will only continue clicking on one task for a finite amount of time before they
go on to something unrelated. The IR(P) values we computed above give us the probability that
our random surfer is at P at any given time.

4. Forward Link Count. For completeness we may want to consider a metric IF(P) that counts the
number of links that emanate from P. Under this metric, a page with many outgoing links is very
valuable, since it may be a Web directory. This metric can be computed directly from P, so IF’(P)
= IF(P). This kind of metric has been used in conjunction with other factors to reasonably identify
index pages [Pirolli 1996]. We could also define a weighted forward link metric, analogous to
IR(P), but we do not consider this here.

5. Location Metric. The IL(P) importance of page P is a function of its location, not of its contents. If
URL u leads to P, then IL(P) is a function of u. For example, URLs ending with ".com" may be
deemed more useful than URLs with other endings, or URL containing the string "home" may be
more of interest than other URLs. Another location metric that is sometimes used considers URLs
with fewer slashes more useful than those with more slashes. All these examples are local metrics
since they can be evaluated simply by looking at the URL u.

As stated earlier, our importance metrics can be combined in various ways. For example, we may define
a metric IC(P) = k1•IS(P, Q) + k2•IB(P), for some constants k1, k2. This combines the similarity metric
(under some given query Q) and the backlink metric. Pages that have relevant content and many
backlinks would be the highest ranked . (Note that a similar approach was used to improve the
effectiveness of a search engine [Marchiori 1997].)

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.