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.