Description
Dataset
You are provided a dataset for this assignment, which you are free to use. You can use your own dataset as well.
1
Assignment
In this assignment we continue building an information retrieval system based on the results of Assignment 1, which was a system that can output a sorted list of term-document pairs.
The task in this assignment is:
- Build an inverted index;
- Enable simple Boolean search; 3) Implement compression techniques.
1. Inverted Index
Input: a file with sorted term-doc pairs Output: inverted index
In this part you would need to take the file containing the sorted list of term-doc pairs and transform it into a simple inverted index. In this assignment you don’t have to worry that the list or the inverted index can be too big for main memory; however, you can take that into account.
Bonus Points: persist the inverted index as a file so you don’t need to rebuild it every time you launch the program.
2. Boolean Search
Input: a search query, an inverted index
Output: a list of documents satisfying the query
Implement a simple AND-based Boolean search, i.e., a query “horse car phone” should be treated as “horse AND car AND phone” and return only documents that contain all three words.
Bonus Points: Implement OR and NOT in addition to AND.
3. Index Compression/Optimization
Implement compression and optimization techniques that were discussed in the lectures. In particular, implement at least the Dictionary-as-a-String approach. Implementing other techniques (blocking, front-coding, skip pointers, variable-length gap encoding) is encouraged.
Compare your search engine performance and memory requirements before and after implementing compression and optimizations. Reflect the comparison in your report.
