Digital Libraries/Crawling

Module name

Crawling

Scope

This module covers the basic concepts of Web crawling, policies, techniques and how this can be applied to Digital Libraries.

Learning objectives:

By the end of this module, the student will be able to:

a. Explain the basic concepts of Web crawling.

b. Explain the architecture of a simple crawler.

c. Explain policies followed by a crawler.

5S characteristics of the module:

a. Stream: HTML , CSS, JavaScript and other web designing languages, text, videos, images and other Internet media type

b. Structure: Refers to the structure of the Web, which in the form of a directed graph called the Web Graph in which the nodes are Web Pages and the edges are the hyperlinks connecting them.

c. Scenarios: Scenarios relates to the process followed by the crawler in order to scans the web and make copies of the pages visited by it.

d. Space: The World Wide Web and the physical storage issues faced by the crawlers such as a search engine repository where the data collected by the crawler is stored.

e. Society : Managers, Computer Programmers academia involved with the development and maintenance of Web Crawlers, bots and computer programs, as well as authors of Web sites.

Level of effort required:

a. Prior Reading : 2 hours

b. In Class Time : 4 hours

1. 2 hours for understanding the basic functions of a crawler along with its working and evaluation.

2. 2 hours for class activity.

Relationships with other modules:

a. 3-a: Collection development/selection policies]]

b. 3-e: (7-e): Web (push) Publishing]]

c. 4-a: Information architecture (e.g. , hypertext, hypermedia)]]

d. 7-a: Indexing and searching

e. 9-f: Cost/economic issues]]

Prerequisite knowledge required:

a. None

Introductory remedial instruction:

a. None

Body of knowledge:

Web Basics

The internet is a worldwide system of interconnected digital networks that use the standard internet protocol Suite( TCP/IP) to connect us all together. It can be thought of as a network of networks consisting of millions of private and public, academic , government , and business networks that are connected together by a large number of electronic and optical network technologies. The internet consists of a vast amount of digital information, the most common of which is the interconnected hypertext documents which makes up the World Wide Web (WWW).

In the late 1980s Sir Timothy John "Tim" Berners-Lee then a scientist at CERN invented the World Wide Web to share information among scientists working in different universities and institutions around the world. However, web usage caught up to such an extent that now a significant amount of the human population has access to it and uses it on a daily basis. The World Wide web is based on a simple client- server design 1) The client which is usually a web browser, communicates with a server through a simple protocol called the HyperText Transfer Protocol(HTTP) and 2)the server which receives a request from a client, responds by sending back the desired information in the form of asynchronous payloads(text, images, audio ,video and other forms of information) encoded in a simple language called the hypertext markup language(HTML).

In order to know how a crawler works, we need to know a little more about the world wide web and its structure. In this example, we shall consider static web pages and try to visualize how they are connected together to better understand how they are crawled. A static web page is a web page whose content does not change from one request to it from the next. As a result, we can view the web as a directed graph consisting of static web pages connected together by hyperlinks in which each web page is considered as a node and each hyperlink is considered as an edge.

• Web Crawlers

• A web crawler is an automated computer program that browses the World Wide Web by following certain policies as mentioned by its creator. Its main purpose is to create a copy of all the web pages visited by it for later analysis by a search engine. The search engine usually will index this for providing faster and efficient searches. A crawler may also be used as a means of automating website maintenance tasks by checking the validity of html links of web pages and the code within it. Another way using the crawler is in a destructive manner. For example, gathering specific types of information from the World Wide Web such as harvesting e-mail addresses (usually for spam).
• A web crawler is known by many names like ants, automatic indexers, bots, and worms and Web spider. The process by which a web crawler browses the World Wide Web is called Web Crawling or spidering. Many sites, especially search engines use this as means of creating a fresh copy of the World Wide Web in their repository

• Inner working of a crawler

• A crawler may be thought of as a bot who roams the World Wide Web by following his master’s commands. A crawler usually starts with one or more URLs which is called the seeds. It picks a URL from this set and downloads the corresponding web page. This fetched page is then processed to extract the digital information as well as the links (each of which points to another page) from this page. The extracted digital information is fed into an indexer. The extracted links are then added to a URL Frontier which consists of web pages which the crawler has not explored yet. This entire process can be visualized as traversing a web graph. The URLs from the frontier are recursively visited based on a set of predetermined policies.

• Crawler Architecture

• The process of crawling is a complex process which can be broken down into a few functional components which work together to make crawling possible. These components are:
• The URL Frontier which is a set of all the URLs which the crawler has not yet explored. It could be called the to-do list of the crawler that contains the list of URLs not visited by the crawler
• A DNS resolution module which is used to determines the web server from which the web page is fetched as specified by the URL.
• A fetch module which is used to retrieve a web page as specified by the URL
• A parsing module, which is used to extract the contents and links from a web page.
• A duplicate elimination module, which determines whether an extracted link is already present in the URL frontier or has already been fetched by the crawler.
• The process of crawling can be performed by a single system or a distributed system with different nodes running simultaneously an instance of this process.

Crawling policies

• In order to crawl the web, we have to be aware of the obstacles that a crawler may face during its crawl. These characteristics of the web are:

a. It’s very large volume

b. It’s really fast rate of change and

c. It’s dynamic page generation

• These characteristics combined together produce a myriad variety of crawable URLs.

Even with the fastest computers and very high bandwidth, downloading the whole World Wide Web may take months. Due to this constraint, crawlers need to prioritize the pages it downloads. The fast rate of change implies that due to the constant updating of web pages, by the time a crawler downloads all the pages from a site, it is highly likely that the web page has been updated or deleted, or that new pages have been added to the website. Another major obstacle that has been faced by many crawlers is the dynamically generated web pages based on user input which makes it difficult for crawlers to avoid retrieving duplicate content. Endless combinations of HTTP GET (URL- based) parameters exist, of which only a small set returns unique content. For example let us consider a simple online shopping portal, which provides different options to users, as specified through HTTP GET parameters in the URL. If there exists five ways to sort the products (eg. Price, popularity ), four choices of thumbnail size and an option to enable or disable product description, then the same set of content can be accessed by forty different URLs, all of which will be linked to the same site. This mathematical combination creates problems for crawlers, as they must parse through all these pages containing relatively small changes in order to fetch unique content.

• As Edwards et al. noted, "Given that the bandwidth for conducting crawls is neither infinite nor free, it is becoming essential to crawl the Web in not only a scalable, but efficient way, if some reasonable measure of quality or freshness is to be maintained."

• The behavior of a crawler is the outcome of a combination of the following policies:

a. a selection policy that states which pages to download,

b. a re-visit policy that states when to check for changes to the pages,

c. a politeness policy that states how to avoid overloading Web sites, and

d. a parallelization policy that states how to coordinate distributed Web crawlers.

• Selection policy

• Due to the large size of the web, even a large search engine can only download a fraction of the publically available Web. A study by Lawrence and Giles showed that no search engine indexes more than 16% of the Web in 1999. Hence, a crawler usually downloads only a part of the World Wide Web. Due to this, it is highly desirable that this fraction contains as many “useful” pages as possible.
• In order to achieve this, the crawler should be able to recognize the importance of a page and prioritize it. Some methods of assigning the importance of a page are described in the next topic. Designing a good selection policy has an additional difficulty; it must work with a fraction of the Web, as the complete set of Web pages is not known during crawling.

a. Restricting followed links: A crawler may only want to visit HTML(static text) pages and avoid all other internet media types. In order to make this possible, a crawler may make a HTTP HEAD request to determine a web resource’s internet media type before requesting the entire page. However, to avoid making numerous HEAD requests, a crawler may examine the URL of a resource and download only those pages ending with a particular sequence of characters like .html, .htm, .asp, .aspx, .php, or a slash. The down side of this strategy is that it may cause numerous HTML Web resources to be unintentionally skipped.

Some crawlers may also avoid URLs containing the character “?” in order to avoid spider traps that may cause the crawler to download an infinite number of URLs from a web site. However, this strategy is unreliable if the site uses URL rewriting to simplify its URLs.

b. Path Ascending crawling: Some crawlers try to download as many resources as possible from a particular Web site. That way a crawler would ascend to every path in each URL that it intends to crawl. For example, when given a seed URL of http://animals.org/eliphant/baby/description.html, it will attempt to crawl /elephant/baby/, /elephant/, and /.

A Path- ascending crawler is very effective in finding isolated resources and resources which would have resulted in no inbound links on a regular crawl.

Many path-ascending crawlers are also known as Harvesters since they're used to "harvest" or collect all the content(like all the photos from a gallery) from a specific page or host.

c. Focused Crawling: A focused crawler or topical crawler is a web crawler that attempts to download pages that are similar to each other and are relevant to a pre-defined topic or set of topics. In Topical crawling, the crawler assumes that the topic is given whereas in focused crawling, the crawler also assumes that some labeled examples of relevant and non relevant pages are available. Topical crawling was first introduced by Menczer whereas focused crawling was first introduced by Chakrabarti.

A focused crawler ideally would like to download only web pages that are relevant to a particular topic and avoid downloading all others. Hence a focused crawler needs to predict the probability that a link to a particular page is relevant before actually downloading the page. One possible way of doing this is to consider the anchor text of links as the predictor.

• Another way to achieve a focused crawl is to determine the relevance of a page after downloading its contents. The relevant pages are indexed and their contained URLs are added to the URL frontier and the pages which fall below a relevance threshold are discarded.

d. Crawling the Deep Web: The deep Web (also called Deepnet,the invisible Web, dark Web or the hidden Web) refers to World Wide Web content that is not part of the surface Web, which is indexed by standard search engines. These pages are usually created by submitting queries to a database. A regular crawler will usually be unable to find such pages unless pointed by a link from another page.

One way to access the deep Web is by using federated search based search engines. Some search tools such as Science.gov are being designed to retrieve information from the deep Web. These tools work by identifying and interacting with searchable databases. Hence they provide us with a means of accessing the content of the deep Web.

• Re-visit policy

• The Web is considered to be very large in volume. Its size coupled with its dynamic nature makes it very difficult to crawl. Even crawling a fraction of the web may take a really long time, usually measured in weeks or months. By the time a crawler has finished a single full cycle of its crawl, they Web would have changed in many ways. Many of the crawled pages would have been updated or deleted whereas some pages would have even been added to the Web.

From the search engines point of view, having an outdated copy of a resource reduces its credibility and reliability. As a result a search engine would like to have an updated copy of the Web. The most used cost functions used to measure this are freshness and age.

• Freshness: This is a binary measure that indicates whether a copy is accurate or not. Hence its value could be either 0 or 1.
• Age: This is a measure which indicates how outdated the local copy is.

One of the main objectives of a crawler is to keep the average freshness of pages in its repository as high as possible, or to keep the average age of pages as low as possible. These two objectives cannot be directly compared. Since in the first case, the crawler is just concerned with how many pages are out-dated, while in the second case, the crawler is concerned with how old the local copies of pages are.

• Next we shall look at two simple revisiting policies:

a. Uniform Policy: Implies re-visiting all pages in the collection with the same frequency, regardless of their rates of change.

b. Proportional Policy: Implies re-visiting more often the pages that change more frequently.

• Politeness policy

• A crawler is capable of retrieving data much quicker and in greater depth than a human can. As a result they can have a crippling effect on the performance of a site. Since a crawler can access multiple pages at the same time at speeds much larger than that designed by the website (for humans), a server would have a really hard time keeping up with these requests especially if multiple crawlers access the website at the same time.
• As noted by Koster, the use of Web crawlers is useful for a number of tasks, but comes with a price for the general community. ::* The costs of using Web crawlers include:

a. network resources, as crawlers require a considerably higher bandwidth and operate for longer periods of time with high degrees of parallelism

b. server overload, since crawlers can access servers that are much higher than an average human can

c. poorly-written crawlers, which can crash servers or routers, or which download pages they cannot handle; and

d. personal crawlers that, if deployed by too many users, can disrupt the whole network and even the Web servers.

• To tackle some of these problems, usually Web servers have both implicit and explicit policies which state the rate at which a crawler can visit a website. These politeness policies must be respected by the crawler. An example of this is the robots exclusion protocol which we have discussed earlier. We could also specify a "Crawl-delay:" parameter in the robots.txt file in order to indicate the delay between requests.

• Parallelization policy

a. Multithreaded Crawler: Sequential crawling may be inefficient as most of the time either the CPU is idle (during disk or network access) or the network interface is idle (during CPU processing). In order to tackle this problem we use Multithreading which optimizes CPU utilization as well as the network bandwidth. In a multithreaded crawler, each thread locks the URL Frontier while selecting a URL that it will crawl. After it has picked a URL, it unlocks the frontier so that other threads can access it and pick a URL. While a URL is added to the frontier, the frontier is again locked to maintain consistency. The locking is necessary in order to prevent duplicates or crawling the same URLs since the Frontier is now shared among many crawling loops.

b. Keeping Crawlers at bay: Many hosts on the World Wide Web place certain portions of their web site off limits to a web crawler. This message is communicated to a crawler through a robots.txt file. This standard is known as the Robots Exclusion Protocol. The robots.txt file is placed at the root of the URL hierarchy of that site so that the crawler reads it at its first contact with a particular site. Below is an example of a robots.txt file that disallows all crawlers except the crawler called “myCrawler” from visiting the URLS that are placed in the file hierarchy starting with the name “/mysite/privateFiles/”

c. URL Normalization: Another important process that we should be aware of is URL normalization. URL normalization is the process by which a URL is modified or standardized as required. URL normalization is used to transform a URL into a normalized or canonical form in order to determine if two syntactically different URLs are equivalent. Web crawlers use URL normalization in order to avoid adding duplicates to the URL frontier.

d. Evaluation of a Crawler: A crawler may be classified as a good crawler depending on the type and the quality of information it fetches. Since the World Wide Web is dynamic and a website may update its pages periodically, it is important that a crawler fetches pages that are “useful”. However, a major problem that a crawler faces is recognizing these useful pages. Since a crawler is an automated program, it should be capable of understanding what the contents of a web page mean and classify them as important or not. Hence in order to evaluate a crawler, we need to see the usefulness of the pages fetched by the crawler as well as the crawl time of a crawler.

Web Page Importance

These are some of the methods that have been used in order to access the importance of a web page and hence its “usefulness”:

a. Keywords in documents: If a page contains some or all the keywords in a particular query, the page may be considered as relevant. We may also consider the frequency of occurrence within the page.

b. Similarity to seed pages: The pages corresponding to the seed URLs are used to measure the importance of the crawled pages. This is done by calculating the cosine similarity of a document (containing seed pages combined together) and the crawled page. This is used as the page’s relevance score.

c. Similarity to a query: Comparing the user query and the resulting pages that are fetched by the crawler and looking at its similarity (whether the user needs are met) gives us an idea of the importance of the web page.

d. Classifier Score: A classifier ( bot ) may be trained by a human to identify the pages that are relevant to the needs of the users. This classifier may then provide automated scores to each crawler page based on its relevance. The training is done by specifying a small sample of relevant pages as positive examples.

e. Link-based popularity: using algorithms such as Page Rank or HITS, which provide popularity estimates of each of the crawled pages. A simpler method would be to use just the number of in-links to the crawled page to derive similar information. Many variations of link based methods using topical weights are choices for measuring topical popularity of pages.

f. Retrieval System Rank: N different crawlers are started from the same seed and allowed to run till each crawler gathers P pages. The entire set of N*P pages collected from the crawler are ranked against the initiating query or description using a retrieval system such as SMART. The rank provided by the retrieval system for a page is used as its relevance score.

Resources

Required readings for faculty

i. Pant, Gautam; Srinivasan, Padmini; Menczer, Filippo (2004), "Crawling the Web” http://web.archive.org/web/20040707144524/http://dollar.biz.uiowa.edu/~pant/Papers/crawling.pdf (12/8/2009)

ii. Christopher D Manning, Prabhakar Raghavan, Hinrich Schutze “An Introduction to Information Retrieval” (Pages 443-469) http://nlp.stanford.edu/IR-book/information-retrieval-book.html (12/8/2009)

iii. Cho, J.; Garcia-Molina, H.; Page, L. (1998-04), "Efficient Crawling Through URL Ordering", Seventh International World-Wide Web Conference, Brisbane, AustraliaBorgman, C. L. (2003). http://ilpubs.stanford.edu:8090/347/ (12/8/2009)

iv. Heydon, Allan, Najork, Marc (1999-06-26) Mercator: A Scalable, Extensible Web Crawler http://web.archive.org/web/20041122071908/http://www.cindoc.csic.es/cybermetrics/pdf/68.pdf (12/8/2009)

v. Cristian Duda,Chong Zhou , Gianni Frey, Donald Kossmann. “AJAXSearch: Crawling, Indexing and Searching Web 2.0 Applications “

http://web.archive.org/web/20091007051536/http://www.dbis.ethz.ch/research/publications/AjaxSearchVLDB08.pdf (12/8/2009)

Required readings for students

i. Pant, Gautam; Srinivasan, Padmini; Menczer, Filippo (2004), "Crawling the Web” http://web.archive.org/web/20040707144524/http://dollar.biz.uiowa.edu/~pant/Papers/crawling.pdf (12/8/2009)

ii. Christopher D Manning, Prabhakar Raghavan, Hinrich Schutze “An Introduction to Information Retrieval” (Pages 443-469) http://nlp.stanford.edu/IR-book/information-retrieval-book.html (12/8/2009)

IR-related resources from Wikipedia and other sources

i. Web Crawler: http://en.wikipedia.org/wiki/Web_crawler (12/8/2009)

ii. Web Crawler: http://www.devbistro.com/articles/Misc/Implementing-Effective-Web-Crawler (12/8/2009)

iii. Focused Crawler: http://en.wikipedia.org/wiki/Focused_crawler (12/8/2009)

Exercises / Learning activities

• In this exercise, we shall be using an open source Web Crawler and assess its effectiveness. A few crawlers that are easy to use have been listed below:

1. PHP Crawler

2. Heritrix Web Crawler.

Students can use NutchWax and WayBack to index and search through crawled data.

• In addition to these we have the following open source crawlers which you can use:

1. Aspseek

2. arachnode.net

3. DataparkSearch

4. GNU Wget

5. GRUB

6. ht://Dig

7. HTTrack

8. ICDL Crawler

9. mnoGoSearch

10. Nutch

11. Pavuk

12. YaCy

• There is no restriction on the type of crawlers used for the exercise. These are just suggestions in order to help the student to choose a crawler.
• Perform a crawl on a website, for example http://www.cs.vt.edu. Make sure that the crawler takes at least an hour to perform the crawl. After the crawl, examine the quality of the web pages fetched by the crawler and if the pages retrieved by the crawler are relevant to your user query. After the analysis prepare a 20 min presentation on the results of your analysis using terms you have recently learnt in this module. You will be graded on your ability of explaining your analysis of the crawl with terms relevant to the module and web crawlers. After the presentation there will be a 10 min question session where other students may ask the presenter with questions regarding their presentation.

• Suggestion to the instructor:

• An instructor may make this exercise more specific by giving a specific crawler to use along with a URL and a user query in order to maintain consistency of the crawled content

Evaluation of learning outcomes

• In their presentation, the students need to analyze and give a brief presentation about their findings based on the content taught in this module. The students should show good understanding of the Web Crawler basics, the Crawler architecture, and Crawler policies

Glossary

• URL: Uniform Resource Locator
• WWW: World Wide Web
• HTTP: Hypertext Transfer Protocol
• Crawler: A Web crawler is a computer program that browses the World Wide Web in a methodical, automated manner.
• Web Page: A webpage or web page is a document or resource of information that is suitable for the World Wide Web and can be accessed through a web browser.
• SMART: Self-Monitoring, Analysis, and Reporting Technology From http://www.wikipedia.org/

Additional useful links

• Some commercial Web Crawlers:

a. Winweb Crawler: http://www.winwebcrawler.com/index.htm (12/8/2009)

b. Spinn3r: http://spinn3r.com/ (12/8/2009)

c. Advanced Site Crawler: http://www.innovative-sol.com/sitecrawler/index.htm (12/8/2009)

d. Website Ripper Copier: http://www.tensons.com (12/8/2009)

Concept map

See VTech Concept Map server under "Dlcurric" folder

Contributors

a. Developers:

• Dr. Edward Fox
• Ashwin S Khandeparker

b. Reviewers:

• Seungwon Yang
• John Ewers
• Tarek Kanan
• Ashwin Palani