CSE 382 Algorithms and Data Structures

Barbara Nostrand, Ph.D.

Electrical Engineering and Computer Science


Laboratory 12 - Mini Search Engine

Introduction

In this project,  you will be designing and implementing a mini search engine.  You are probably familiar with Google,  Altavista or Yahoo,  which are some of the most popular search engines that you can find on the Web.  The task performed by a search engine is,  as the name says,  to search through a collection of documents.  Given a set of texts and a query,  the search engine will locate all documents that contain the keywords in the query.  The problem may be therefore reduced to a search problem, which can be efficiently solved with the data structures we have studied in this course. 

Objective

Your task is to design and implement an algorithm that searches a collection of documents.  You will be provided with a set of 50 documents and a set of sample queries.  You have the freedom to select the data structures and algorithms that you consider to be more efficient for this task.  Of course,  you will have to justify your decisions.  First,  you will process the documents and store their content (i.e. words / tokens) in the data structures that you selected (in information retrieval,  this phase is called indexing).  Next,  for every input query,  you will process the query and search its keywords in the documents,  using the previously implemented data structures and an algorithm of your choice.  (This phase is called retrieval.)  For each such query,  you will have to display the documents that satisfy the query. 

The queries may contain simple Boolean operators,  that is AND and OR,  which act in a similar manner with the well known analogous logical operators.  For instance,  a query:  "Keyword1 AND Keyword2" should retrieve all documents that contain both these keywords (elements).  "Keyword 1 OR Keyword 2" instead will retrieve documents that contain either one of the two keywords. 

Example

Consider the following sample documents: 
Doc1: I like the class on data structures and algorithms.
Doc2: I hate the class on data structures and algorithms.
Doc3: Interesting statistical data may result from this survey.
Here are the answers to some queries: 
Query 1: data
Doc1, Doc2, Doc3
Query2: data AND structures
Doc1, Doc2
Query 3: like OR survey
Doc1, Doc3

Hints

First,  download the sample documents,  and take a look at their format.  You will have to parse these files.  You may ignore all lines starting with "<",  these SGML tags are similar to HTML tags and are useful for certain tasks,  but you will probably not find them very useful in this project.  The punctuation is already separated from the words,  so you do not have to worry about that.  You will have to read one word at a time and add it to your data structure.  As data structures,  you may consider using dictionaries / hashtables,  trees – such as 2-4 trees,  AVL trees,  balanced binary search trees.  Any other data structures are admissible as well – although,  again,  you have to be able to justify your selection.  For every word,  you should store a list of documents where it occurs,  in order to allow for efficient searches and Boolean operators later on. 

What to turn in

There are three main parts in this project,  all of them contributing to the final project grade. 

  1. You will have to write a project report (about 7-10 typed pages – single space – 12pt font) that includes: 
  2. You will have to upload a fully working program,  written in Java,  that you can provide with a query,  and obtain the list of documents.  It is mandatory that you include a README file,  as detailed as possible,  including compilation and running instructions.  Your programs must be fully documented,  that is they should include. 
  3. detailed comments on what is included in each file and what each method does. 

Grading

Extra Credit

  • Up to 15 points extra credit may be given if you handle some of these issues: 

    Notes

    Available Files

    documents.tarsample.queries.txtstopwords.txt

    Acknowledgements

    This laboratory project was originally developed by Rada Mihalcea
    Last modified: 2008 APR 25
    bnostran@syr.edu