CSE 333 Homework 3

Starter Videos

The following videos are intended to help you double-check your understanding of the index file format used in HW3 as well as demonstrate the debugging process. It is recommended that you watch these AFTER reading through the specs.

1. Index File Overview
2. Index File Debugging

Note: You can click on the labeled timestamps in the "Contents" menu to jump between sections of the video.

Part A: Memory-to-File Index Marshaller

Keeping a search engine index in memory is problematic, since memory is expensive and also volatile. So, in Part A, you're going to write some C++ code that takes advantage of your HW2 implementation to first build an in-memory index of a file subtree, and then it will write that index into an index file in an architecture-neutral format.

What do we mean by architecture-neutral? Every time we need to store an integer in the file's data structure, we will store it in big endian representation. This is the representation that is conventionally used for portability, but the bad news is that this is the opposite representation than most computers you use: x86 computers are little endian. So, you will need to convert integers (whether 16-bit, 32-bit, or 64-bit) into big endian before writing them into the file. We provide you with helper functions to do this.

The good news is that we're going to keep roughly the same data structure inside the file as you built up in memory: we'll have chained hash tables that are arrays of buckets containing linked lists. And, our inverted index will be a hash table containing a bunch of embedded hash tables. But, we need to be very precise about the specific layout of these data structures within the file. So, let's first walk through our specification of an index file's format. We'll do this first at a high level of abstraction, showing the major components within the index file. Then, we'll zoom into these components, showing additional details about each.

At a high-level, the index file looks like the figure on the right. The index file is split into three major pieces: a header, the doctable, and the index. We'll talk about each in turn.

Header

An index file's header contains metadata about the rest of the index file:

1. The first four bytes of the header are a magic number, or format indicator. Specifically, we use the 32-bit number 0xCAFEF00D. We will always write the magic number out as the last step in preparing an index file. This way, if the program crashes partway through writing one, the magic number will be missing, and it will be easy to tell that the index file is corrupt.
2. The next four bytes are a checksum of the doctable and index regions of the file. A checksum is a mathematical signature of a bunch of data, kind of like a hash value. By including a checksum of most of the index file within the header, we can tell if the index file has been corrupted, such as by a disk error. If the checksum stored in the header doesn't match what we recalculate when opening an index file, we know the file is corrupt and we can discard it.
3. The next four bytes store the size of the doctable region of the file. The size is stored as a 32-bit, signed, big endian integer.
4. The final four bytes of the header store the size of the index region of the file, in exactly the same way.

Doctable

Let's drill down into the next level of detail by examining the content of the doctable region of the file. The doctable is a hash table that stores a mapping from 64-bit document ID to an ASCII string representing the document's filename. This is the docid_to_docname HashTable that you built up in HW2, but stored in the file rather than in memory.

The doctable consists of three regions; let's walk through them, and then drill down into some details:

1. num_buckets: This region is the simplest; it is just a 32-bit big endian integer that represents the number of buckets inside the hash table, exactly like you stored in your HashTable.
2. An array of bucket_rec records: This region contains one record for each bucket in the hash table. A bucket_rec record is 8 bytes long, and it consists of two four-byte fields. The chain len field is a four byte integer that tells you the number of elements in the bucket's chain. (This number might be zero if there are no elements in that chain!) The bucket position field is a four-byte integer that tells you the offset of the bucket data (i.e., the chain of bucket elements) within the index file. The offset is just like a pointer in memory or an index of an array, except that it points within the index file. For example, an offset of 0 would indicate the first byte of the file, an offset of 10 would indicate the 11th byte of the file, and so on.
3. An array of buckets: This region contains one bucket for each bucket in the hash table. A bucket is slightly more complex; it is a little embedded data structure. Specifically, each bucket contains:
   • An array of element positions: Since elements are variable-sized, rather than fixed-sized, we need to know where each element of the bucket lives inside the bucket. For each element, we store a four-byte integer containing the position (i.e., offset) of the element within the index file.
   • An array of elements: At each position specified in the element positions array lives an element. Since this is the docid-to-filename hash table, an element contains a 64-bit document ID and a filename. The document ID is an unsigned, big endian integer. Next, we store a 16-bit (2-byte) signed, big endian integer that contains the number of characters in the file name. Finally, we store the filename characters (each character is a single ASCII byte). Note that we do NOT store a null-terminator at the end of the filename; since we have the filename length in an earlier field, we don't need it!

Index

The index is the most complicated of the three regions within the index file. The great news is that it has pretty much the same structure as the doctable: it is just a hash table, laid out exactly the same way. The only part of the index that differs from the doctable is the structure of each element, so let's focus on that.

An index maps from a word to an embedded docID hash table, or docID table. So, each element of the index contains enough information to store all of that. Specifically, an index table element contains:

1. A two-byte signed integer that specifies the number of characters in the word.
2. A four-byte signed integer that specifies the number of bytes in the embedded docID table.
3. An array of ASCII characters that represents the word; as before, we don't store a NULL terminator at the end.
4. Some variable number of bytes that represents the docID table.

So, all we need to understand now is the format of the docID table. We're sure its format will come as no surprise at this point...

docIDtable

Like the "doctable" table, each embedded "docIDtable" table within the index is just a hash table! A docIDtable maps from a 64-bit docID to a list of positions with that document that the word can be found in. So, each element of the docID table stores exactly that:

1. A 64-bit (8-byte) unsigned integer that represents the docID.
2. A 32-bit (4-byte) signed integer that indicates the number of word positions stored in this element.
3. An array of 32-bit (4-byte) signed integers, sorted in ascending order, each one containing a position within the docID that the word appears in.

So, putting it all together, the entire index file contains a header, a doctable (a hash table that maps from docID to filename), and an index. The index is a hash table that maps from a word to an embedded docIDtable. The docIDtable is a hash table that maps from a document ID to a list of word positions within that document.

Part A Instructions

The bulk of the work in this homework is in this step. We'll tackle it in parts.

1. Change to the directory containing your CSE 333 GitLab repository. Use git pull to retrieve the new hw3/ folder for this assignment. Look around inside of hw3/ to familiarize yourself with the structure.
   • The symbolic link test_tree/ is still pointing to the proj_docs/test_tree/ directory so you have access to text documents to index. This means any additional testing files that you created in hw2/test_tree/ are still readily available to you in HW3!
   • There is a new subdirectory/symbolic link called unit_test_indices/ (that also happens to point into the proj_docs/ directory). This directory contains properly formatted/written file indices that can be used for comparison with the output of your Part A, as well as for use with your Part B and C (even if your Part A implementation is still broken!).
   • There is a subdirectory called hw3fsck/, which contains the source code for an executable of the same name. "fsck" is short for "file system check," and this is a utility that can help check the contents of your produced index files.
2. Next, run make to compile the three HW3 binaries. One of them is the usual unit test binary. Run it, and you'll see the unit tests fail, crash out, and you won't yet earn the automated grading points tallied by the test suite.
   • The Makefile will create two subdirectories called libhw1/ and libhw2/. These contains symbolic links to header files and archives from the previous two homework.
   • By default, your HW3 code will compile with the staff solution binaries for HW1 and HW2. THIS MIRRORS THE WAY THAT YOUR HW3 IMPLEMENTATION WILL BE GRADED. If you'd like to see how things work with your own HW1 and HW2 solutions, edit line 15 in the HW3 Makefile to set USE_SOLUTION_BINARIES to false instead. Just remember to change it back before you do your final testing before submission.
   • The Makefile also builds the hw3fsck/hw3fsck executable referenced in Step 6 below.
3. Now, take a look inside Utils.h and LayoutStructs.h. These header files contains some useful utility routines and classes you'll take advantage of in the rest of the assignment. We've provided the full implementation of Utils.cc. Next, look inside WriteIndex.h; this header file declares the WriteIndex() function, which you will be implementing in this part of the assignment. Also, look inside buildfileindex.cc; this file makes use of WriteIndex() and your HW2 CrawlFileTree(), to crawl a file subtree and write the resulting index out into an index file. Try running the solution_binaries/buildfileindex program to build one or two index files for a directory subtree, and then run the solution_binaries/filesearchshell program to try out the generated index file.
4. Finally, it's time to get to work! Open up WriteIndex.cc and take a look around inside. It looks complex, but all of the helper routines and major functions correspond pretty directly to our walkthrough of the data structures above. Start by reading through WriteIndex(); we've given you part of its implementation. Then, start recursively descending through all the functions it calls, and implement the missing pieces. (Look for STEP: in the text to find what you need to implement.)
5. Once you think you have the writer working, compile and run the test_suite as a first step. Next, use your buildfileindex binary to produce an index file (we suggest indexing something small, like ./test_tree/tiny as a good test case). After that, use the solution_binaries/filesearchshell program that we provide, passing it the name of the index file that your buildfileindex produces, to see if it's able to successfully parse the file and issue queries against it. If not, you need to fix some bugs before you move on!
   Aside: If you write the index files to your personal directories on a CSE lab machine or on attu, you may find that the program runs very slowly. That's because home directories on those machines on a network file server, and buildfileindex does a huge number of small write operations, which can be quite slow over the network. To speed things up dramatically we suggest you write the index files into /tmp, which is a directory on a local disk attached to each machine. Be sure to remove the files when you're done so the disk doesn't fill up.
6. As an even more rigorous test, try running the hw3fsck program we've provided in solution_binaries against the index that you've produced. hw3fsck scans through the entire index, checking every field inside the file for reasonableness. It tries to print out a helpful message if it spots some kind of problem. Once you pass hw3fsck and once you're able to issue queries against your file indices, then rerun your buildfileindex program under valgrind and make sure that you don't have any memory leaks or other memory errors.

Part B: Index Lookup

Now that you have a working memory-to-file index writer, the next step is to implement code that knows how to read an index file and lookup query words and docids against it. We've given you the scaffolding of the implementation that does this, and you'll be finishing our implementation.

Part B Instructions

1. Start by looking inside FileIndexReader.h. Notice that we're now in full-blown C++ land; you'll be implementing constructors, manipulating member variables and functions, and so on. Next, open up FileIndexReader.cc. Your job is to finish the implementation of its constructor, which reads the header of the index file and stores various fields as private member variables. As above, look for "STEP:" to figure out what you need to implement. When you're done, recompile and re-run the test suite. You should pass all the tests for test_fileindex_reader.cc once you have implemented FileIndexReader successfully.
2. Next, move on to HashTableReader.h. Read through it to see what the class does. Don't worry about the copy constructor and assignment operator details (though if you're curious, read through them to see what they're doing and why). This class serves as a base class for other subclasses. The job of a HashTableReader is to provide most of the generic hash-table lookup functionality; it knows how to look through buckets and chains, returning offsets to elements associated with a hash value. Open up HashTableReader.cc. Implement the "STEP:" components in the constructor and the LookupElementPositions function. When you're done, recompile and run the unit tests to see if you pass test_hashtablereader.cc unit test.
3. Now it's time to move on to DocTableReader.h. Read through it, and note that it is a subclass of HashTableReader. It inherits LookupElementPositions() and other aspects, but provides some new functionality. Next, open up DocTableReader.cc, and implement the "STEP:" functionality. See how well you do on its unit test (and valgrind) when you're done.
4. Next, lets move on to IndexTableReader.h. Read through it and understand its role. Next, open up IndexTableReader.cc and implement the "STEP:" functionality. Test against the unit tests (and valgrind).
5. Next, do the same with DocIDTableReader.h and DocIDTableReader.cc.
6. We're almost there! Open up QueryProcessor.h and read through how it is supposed to work. Check out test_queryprocessor.cc for more information. Now open up QueryProcessor.cc and read through our implementation of the constructor and destructor.
   This part of the assignment is the most open-ended. We've given you the function definition for ProcessQuery(), and also a clue about what you should be building up and returning. But, we've given you nothing about its implementation. You get to implement it entirely on your own; you might want to define helper private member functions, you might want to define other structures to help along the way, etc.; it's entirely up to you. But, once you're finished, you'll need to pass our unit test to know you've done it correctly.
   • Hint #1: You should be able to take inspiration from what you did to implement the query processor in HW2. Here, it's only a little bit more complicated. You want to process the query against each index, and then intersect each index's results together and do a final sort (use the STL's sort). Remember that processing a query against an index means ensuring all query words are present in each matching document, and remember how ranking works. Then, once you have query results from each index, you'll append them all together to form your final query results.
   • Hint #2: Once you think you have this working, move on to Part C and finish our filesearchshell implementation. You'll be able to test the output of your filesearchshell against ours (in solution_binaries/) as a final sanity check.
7. Now would be a great time to run valgrind over the unit tests to verify you have no memory leaks or memory errors.

Part C: Search Shell

For Part C, your job is to implement a search shell, just like in HW2, but this time using your HW3 infrastructure you completed Parts A and B.

1. Open up filesearchshell.cc and read through it. Note that unlike Parts A and B, we have given you almost nothing about the implementation of the filesearchshell besides a really long (and hopefully helpful) comment. Implement filesearchshell.cc.
2. Try using your filesearchshell binary. You can compare the output of your binary against a transcript of our solution. The transcripts should match precisely, except perhaps for the order of equally ranked matches. You can also walk your filesearchshell against a very tiny index (tiny.idx) in the debugger to see if it's reading the correct fields and jumping to the correct offsets.
3. Also, note that you can hit control-D to exit the filesearchshell. filesearchshell ought to clean up all allocated memory before exiting. So, run your filesearchshell under valgrind to ensure there are no leaks or errors.

Bonus Tasks

If you want to do any of the bonus parts, first create a hw3-submit tag in your repository to mark the version of the assignment with the required parts of the project. That will allow us to more easily evaluate how well you did on the basic requirements of the assignment. REMINDER: you may not modify the header files for the normal submission. Any bonus you do most not be present in the hw3-submit tag, otherwise it could mess up the results of your submisison when we go to grade it.

Then, when you are done adding additional bonus parts, create a new tag hw3-bonus after committing your additions, and push the additions and the new tag to your GitLab repository. If we find a hw3-bonus tag in your repository we'll grade the extra credit parts; otherwise we'll assume that you just did the required parts. For these tasks you may modify the header files to add additional members, but do not modify the existing ones and do not have these changes show up under your hw3-submit tag, these changes should only be present under hw3-bonus.

1. (Easy): You've probably noticed that the books seem to be consistently ranked higher than other document types in the corpus. This is for a pretty simple reason: books are long, so any given query word will, on average, appear more often in a book than in an email message, inflating the rank of the book. Solve this problem by normalizing the rank contribution of a word within a document by the document length; you'll have to modify the information calculated by hw2 and stored by hw3. In other words, instead of defining the rank contribution of a word in a document to be the word frequency, definie it to be the (word frequency) / (number of words in the document). Do an informal study that evaluates whether this ranking is better or worse, and present your evidence.
2. (Medium): Normalized term frequency is a better ranking function, but it also has a flaw: some words (e.g., "the" or "person") are inherently more frequently used than others (e.g., "leptospirosis" or "anisotropic"). There is a different ranking contribution function called "tf-idf", or term frequency inverse document frequency, that tries to compensate for this. Calculating tf-idf involves keeping track of how often a word appears across an entire corpus of documents, and normalizing term frequency within a document by the frequency across all documents. So, td-idf measures how much more frequently than average a word appears in a given document (more info on tf-idf). Implement tf-idf ranking. You'll have to populate a new hashtable for corpus word frequency and incoporate it into the index file format. Do an informal study that evaluates whether this ranking is better or worse than term frequency, and present your evidence.
3. (Hard): Use valgrind to do a performance analysis of hw3 query processing, and identify any major performance bottlenecks. If you find some obvious performance bottlenecks, attempt to optimize the code to reduce them. Present graphs that demonstrate the performance before and after your optimization, and the evidence you used to decide what to optimize.