CS6200: Information Retrieval

Homework 1

Return to basic course information.

Assigned: Monday, September 15
Due: Email TAs with subject "CS6200 HW1" by Friday, September 26, 11:59 p.m.

Instructions

1. If you collaborated with others, you must write down with whom you worked on the assignment. If this changes from problem to problem, then you should write down this information separately with each problem.
2. Submit the requested written answers, code, and instructions to the TAs on how to (compile and) run the code.

Problems

1. [5 points] Document filtering is an application that stores a large number of queries or user profiles and compares these profiles to every incoming document on a feed. Documents that are sufficiently similar to the profile are forwarded to that person via email or some other mechanism.

   Explain the major differences compared to a search engine. Consider issues such as specific efficiency problems and the usefulness of ranking in a filtering application.

2. [25 points] Focused Crawling

   Implement your own web crawler, with the following properties:

   • Be polite and use a delay of at least one second between requests to the web server.
   • You should start from the seed document http://en.wikipedia.org/wiki/Gerard_Salton, the Wikipedia article on Gerald Salton, an important early researcher in information retrieval.
   • You should only follow links with the prefix http://en.wikipedia.org/wiki/. In other words, do not follow links to non-English articles or to non-Wikipedia pages.
   • Do not follow links with a colon (:) in the rest of the URL.
   • Do not follow links to the main page http://en.wikipedia.org/wiki/Main_Page.
   • You may use existing libraries to request documents over HTTP.
   • Otherwise, you should implement your own code to extract links, keep track of what you've crawled, and decide what to crawl next.
   • Crawl to at most depth 3 from the seed page. In other words, you should retrieve the seed page, pages it links to, and pages those pages link to.
   • Your crawler should take two arguments: the seed page and an optional "keyphrase" that must be present, in any combination of upper and lower case, on any page you crawl. If the keyphrase is not present, stop crawling. This is a very simple version of focused crawling, where the presence or absence of a single feature is used to determine whether a document is relevant.

   Hand in your code and instructions on how to (compile and) run it. In addition, hand in two lists of URLs:

   1. the pages crawled when the crawler is run with no keyphrase, in other words all Wikipedia pages meeting the requirements above to a depth of 3 from the starting seed; and
   2. the pages crawled when the keyphrase is "information retrieval".

   What proportion of the total pages were retrieved by the focused crawler for "information retrieval"? Keep in mind that this will be a significant overestimate of the prevalence of Wikipedia articles on information retrieval.