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;