Database and Information Retrieval

Question 1: Suppose you have joined a search engine development team to design a search algorithm based on both the Vector model and the Boolean model. You are supposed to collect unstructured documents for the following topics, and apply an index technique to convert them into an inverted index.

Please collect 3 documents (less than 30 words for each) in three different topics. Topics are listed as follows, you can also choose some other topics you prefer.

• Science
• Computer Vision
• Search Engine
• Database
• Security and privacy.

An example of document:

"Google is the most widely used Web search engine in the World. It claims to be the World's most comprehensive search engine, indexing over 2.4 billion Web pages."

1. Creating the inverted index. In the process of creating the inverted index, please complete the following steps:

a. Find a stopword list in the Internet and remove all stopwords and punctuation from those three documents.

Then apply Porter's stemming algorithm to all documents. Note that there are plenty of online stemming applications available, and you may use Porter algorithm for this question. The output will be a set of stemmed terms.

b. Create a merged inverted list including the within-document frequencies for each term.

c. Use the index created in step (b) to create a dictionary and the related posting file.

d. You may like to test the inverted index by using some keywords, please select some keywords from the documents. For example: google, web, search.

2. Boolean and Vector queries.

a. Please design three Boolean queries, (for example, web AND search) and list the relevant documents for each query.

b. Please use the Vector model to query on the inverted index, and compare the result with the Boolean model. (Hint: you can use cosine similarity and set a similarity threshold)

Question 2 (IR Evaluation): For this exercise, you are required to evaluate the performance of different search engines.

First, please find two search engines you are familiar with, such as Google, Bing, Yahoo!, etc.

Second, please choose a target in the following groups, and design two queries to search in both search engines.

The target is chosen by the last number of your student ID. For example, if your student ID ends with the number is 1, please choose target 1; if it is 0, please choose target 10.

• Target 1: obtain the unit guide of SIT771.
• Target 2: obtain the unit guide of SIT772.
• Target 3: obtain the unit guide of SIT773.
• Target 4: obtain the unit guide of SIT774.
• Target 5: obtain the price of the new Macbook.
• Target 6: obtain the price of the new iPhone.
• Target 7: obtain the price of a Lenovo Laptop.
• Target 8: obtain the install document of MongoDB.
• Target 9: obtain the manual of MongoDB.
• Target 10: obtain the operation guide of MongoDB.

Select the first 20 results in both search engines, if they return the target, then mark them as relevant documents, otherwise, they are irrelevant. The following exercises are based on your search results.

a. List your target and designed search queries (you can use any keywords you think are related to the target).

For Search Engine 1, plot the precision versus recall curves for Query 1 and Query 2, interpolated to the 11 standard recall levels.

Also plot the average precision versus recall curve for Search Engine 1 (all three curves should be on a single chart).

b. For Search Engine 2, plot the precision versus recall curves for Query 1 and Query 2, interpolated to the 11 standard recall levels.

Also plot the average precision versus recall curve for Search Engine 2 (all three curves should be on a single chart, but a separate chart from that used in part (a)).

c. Plot the averages for Search Engine 1 and Search Engine 2 on a separate chart, and compare the algorithms in terms of precision and recall. Which search engine do you think is superior? Why?