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].)