Text index and search

CSC263/463

1. Introduction

In this assignment, you will be experimenting with keyword search queries. We will utilize a library, Xapian, to index the metadata of data sets of Socrata open data portal, particularly the description and name of data sets. You will be implementing a (command line) interface to search with keywords in names and descriptions.

2. Getting prepared

You need to download the appropriate content before getting started with this assignment:

  1. You need to install and configure the Xapian library. Refer to the tutorial.
  2. You need to download the data set. The data set can be found here. This data set contains about 40,000 entries. The data set (after uncompression) is just a plain text file.
  3. The format is that all even lines are names, and odd lines are the description of the data set.

    data set name 1
    description for data set 1...
    data set name 2
    description for data set 2...
    data set name 3
    description for data set 3...
    ...

3. Building an indexer

You are to build an inverted index on 80,000 words (except stop words) in the name and descriptions. Use the list of stopwords to eliminate very frequent words in the corpus. Note that the index is built on the tokens in names and descriptions. This index will help to retrieve the data sets that have a query word in descriptions or names.

The indexer should be an executable.

metadata_indexer <dataset_metadata> <index_name>

The executable should report the time it takes to index the entries.

Note that Some effort should be spent on cleaning the words in the metadata. Punctuations, white spaces, and other nonstandard characters should be properly dealt with.

4. Building a searcher

You are to build a searcher that searches the metadata of data sets using keywords. The searcher should be an executable.

metadata_search <index_name> <top-k> <keyword1> <keyword2> ...

If the keyword starts with '+', then its an AND query term, otherwise it's an OR query term. It should display:

  1. the amount of time it took to complete the search
  2. the top-k data set names and their data set descriptions
  3. for each matched description, the relevant keyword should be highlighted. Highlighting can be done by adding HTML tags around the keywords, and display the search result in a browser, or simply surround the matched keywords using =, e.g. ===NY State===.

5. Using keyword search for set similarity search

Consider sets Q and X. The similarity of Q and X can be defined as the cardinality of their overlap. $$ similarity(Q, X) = |Q \cap X| $$

You are to write a program using keyword search functionalities of xapian library that finds top-K most similart sets to a query set Q. Consider set cardinalities 2, 20, 100, 250, 500. Generate 30 random sets for each cardinality. The sets should be random samples from the indexed words. Report the average time of finding top-K most similar data set name + descriptions.

6. Organize your submission.

Plots for:

  • Indexing time versus data size

    • Vary the number of entries in the metadata file, and measure the respective indexing time. Consider the following corpus sizes: 500, 10000, ..., 40000.

    • Plot the indexing time (y-axis) versus the number of data sets indexed (x-axis).

  • Search time versus data size:

    • Plot the search time (y-axis) versus the number of data sets in the index (x-axis). Consider the following corpus sizes: 500, 10000, ..., 40000.
  • Search time versus number of AND-keywords in the query

    • Plot the search time (y-axis) versus the number of AND-terms in the query. Consider the following corpus sizes: 2, 5, 10, 15, 20
  • Search time versus number of OR-keywords in the query

    • Plot the search time (y-axis) versus the number of OR-terms in the query.
  • Plot the top-K search time (y-axis) versus the cardinality of the query set. Consider K = 10.

  • [Optional] Plot the top-K search time (y-axis) versus K for a query set. Consider the following K values: 2, 10, 20, 25, 40.

7. Submission

Submit your code as .tar file to the BlackBoard (using assignment name A2).