Search Technology (COSC 2306)

Semester 2 - 2009

Course Description

Text search is a fundamental problem in computer science. Applications of sequence and set-based search include web search engines, genomics, computational biology, network intrusion detection, deep-packet inspection, and many others. Search is now considered a mature research area, and a great variety of practical and theoretical algorithms are known. However, efficient search in massive datasets remains an interesting problem with tangible applications.

In this course we will investigate various state-of-the-art algorithms and data structures which support efficient search in massive data collections. In particular, we will focus on algorithms which exploit the memory hierarchy, provide approximate results, or use data compression to reduce the amount of information processed. Our exposition will include the theoretical analysis as well as practical implementation aspects of the algorithms.

Lecture Material

Date Topic Content
July 21, 2009 Introduction & Requirements
July 28, 2009 Data Compression
Aug 4, 2009 Paper Selection Papers
Aug 11, 2009 On-line Search Algorithms
Aug 18, 2009 Inverted Indexes
Aug 25, 2009 Paper Presentations Presenters
Sep 1, 2009 Semester Break
Sep 8, 2009 Paper Presentations Presenters
Sep 15, 2009 Self-Indexes
Sep 22, 2009 Wavelet Trees
Sep 29, 2009 Project Work Project Specification
Oct 6, 2009 Project Work
Oct 13, 2009 Project Presentations

*The scribe pack here was largely written by Erik Demaine for his advanced data structures class. I provide the template here only as an example of conscientious scribing.

Return to JSC Teaching

Last Update: 1 Dec 2009