Homework 3

Assignment: Write a program (possibly based on your solution to Homework 2) that computes the size of the uncompressed and compressed indices for the umbc-crawl collection.

Goal: To understand the mechanics and implications of index compression for Phase I of the project.

Due Date: Tuesday, October 1, 2002.

Description

First, adapt your Homework 2 solution to compute the size of an uncompressed index of the umbc-crawl collection. Use the same space assumptions as you made in Homework 2. This will necessitate re-examining many assumptions you were able to make in Reuters-21578 about the quality and layout of the collection:

• In umbc-crawl, each file is a single web page and therefore will be considered a single document for purposes of this assignment.
• Actually, I lied a little there. Not all the files are actually HTML web pages, some are binary files which you may not want to index. So, you will need to look at what files there are, and select which ones to "index".
• You no longer have to worry about identifying the beginning and end of each document, since the file boundaries will suffice, but you may want to re-evaluate your term selection approaches in this messier collection.

Because of these differences, your program will need to report the number of documents and unique words.

There are several files at the top of /data/nicholas2/ian/umbc-crawl which you may find helpful:

• README: a description of the crawl mechanism.
• crawl-files: a listing of all the files in the collection, one per line.
• types: a count of the file types in the collection.
• types-mime: a count of the MIME types of the files in the collection. (both of these as reported by file(1)).

After you have done the above, modify your program to compute the size of the index as if it were compressed. Do this for two index compression schemes:

1. D-gaps: delta; Counts: gamma; (Offsets: delta)
2. D-gaps, counts, (and offsets) with variable-byte encoding.

Counting offsets is optional, but recommended if you're planning on storing word offsets in your project!

Note that the size of the lexicon will not change, only the size of the inverted file.

What to turn in

You will turn in a HARD-COPY listing of your program(s) and your output giving the estimate of the space needed for these umbc-crawl indices. Don't forget to report the number of unique words and documents, since depending on which files you index this may vary from person to person. Please make sure your name is on every page and that everything is stapled securely together.

Homework is due at the beginning of class. No late homework will be accepted.