The purpose of this assignment is to select and apply a heuristic search algorithm for finding information in real-time on the web.

The task is to design and implement a web crawler that finds web pages containing a desired type of content.  For example, one specific objective might be to find mp3 files containing music by Led Zeppelin.  Another specific objective might be to find resumes of software engineers posted less than a week ago.  You should choose an interesting objective, but also make your software reusable for other objectives.

Your principal research contribution should be an intelligent search algorithm that uses heuristic knowledge to decide which links to explore next, attempting to find as many pages with the desired content as quickly as possible, while exploring as few unnecessary other pages as possible.

For an overview of the issues involved in this project, see Efficient Web Spidering with Reinforcement Learning by Jason Rennie and Andrew McCallum, ICML'99.  Note that the algorithm ultimately proposed by this paper is a simple approximation of reinforcement learning that resembles a standard non-adaptive heuristic search method.  For this project, you should not attempt to implement any learning or adaptiveness.

See also Focused Crawling Using Context Graphs by M. Diligenti, F. Coetzee, S. Lawrence, C.L. Giles, M. Gori, VLDB'2000.  In general, whenever you are reading technical papers, and especially when you are only looking for relevant ideas to use and/or cite, remember that you do not need to understand the whole paper.  Almost always, most of what you need is in just part of the paper.  Usually, the most important and useful ideas are near the beginning and are less technical.  Often you do not need to understand the details of someone else's technical paper.  However, remember that all the details in any paper you write must be exactly correct.

You should not attempt to build a web crawler from scratch.  Instead, you should reuse existing software as much as possible while adding your own heuristic search algorithm.  Here are recommended starting points:

• WebSPHINX is a crawler implemented in Java.  It is documented well and the source code can be reused freely.  However the code appears to have memory leaks, and it is vulnerable to the bugs that are numerous in most Java implementations.
• The Parallel LWP User Agent is a Perl library that provides the important functions needed to implement a web crawler.  For a full example of how to use this library, with explanations, see Parallel User Agents for Link Checking by Randal L. Schwartz.
• Other crawler toolkits available for reuse are listed at the bottom of the WebSPHINX page.
• PHP is a scripting language for writing web applications that is easier to use than Perl.

Be sure that your web crawler does not cause excessive load on any servers or network connections.  For a discussion of the systems programming issues involved in creating a web crawler, see the papers of the Mercator project.  For a very different approach to crawling the web, see the InfoSpiders project of Filippo Menczer (UCSD CSE Ph.D., 1998).

Some of the issues to consider in your work and to discuss in your paper include the following:

• How does your heuristic search algorithm know to visit pages that do not contain the desired content, but are likely to lead towards it?  For example, a person's home page is not his or her resume, but is likely to link to it.
• Most heuristic search algorithms aim to find a single shortest path to a single goal node.  How must a heuristic search algorithm be different when the aim is to find multiple goal nodes?  When the total number of nodes explored is to be minimized, not the number of nodes on the direct path to a goal node?

The most important part of your paper should be a description of the results of experiments performed with your software.  Use the papers mentioned above as inspiration for the design of your experiments.  Make sure that the experiments are easy to understand, so that the implications of the results obtained are as clear as possible.  The experiments may be preliminary and small in scale, but they should be designed so that you could perform similar definitive experiments if time and resources were available.  For more information on how to design experiments and how to report their results, see these Final Project Report instructions written by Dale Schuurmans of the University of Waterloo.

All your work should be described in a well-written report that follows all the CSE 250A guidelines.  As an appendix to your report, you should attach a printout of your software, which should be adequately commented and documented.  Reports will be evaluated with these grading criteria.

The authors of one or more of the best reports submitted will be asked to revise their report(s) for distribution to all CSE 250A students.  These authors will receive extra credit of 25% of the total credit available for the project, and they will be encouraged to submit a paper for publication, if appropriate.