max planck institut
mpii logo Minerva of the Max Planck Society

Seminar: Searching with Suffix Arrays WS 06/07

Holger Bast, Building 46 (MPI), Room 320; Ingmar Weber, Building 46 (MPI), Room 321; Debapriyo Majumdar, Building 46 (MPI), Room 314.


Suffix Arrays are an elegant and powerful algorithmic technique for searching patterns in strings fast. In this lecture, we explore the power of suffix arrays for building a search engine. This is challenging, because none of the works on suffix arrays directly addresses this concrete application. The format of the seminar will be similar to that of last year's seminar.


Friday afternoon, 14.15 - 15.45 h in room 024 or room 022 (base floor) of MPII. Check the Wiki for the room of the next lecture.


Here is the link to the seminar Wiki.


Exercise Sheet 1 (your first suffix array), Exercise Sheet 2 (paper by Manbers and Myers), Exercise Sheet 3 (suffix array versus inverted index), Exercise Sheet 4 (backward and forward arrays/functions), Exercise Sheet 5 (empirical entropy), Exercise Sheet 6 (bit rank and Burrows-Wheeler transform), Exercise Sheet 7 (searching in a sorted sequence in external memory), Exercise Sheet 8 (inverted index and suffix arrays in external memory), Exercise Sheet 9 (suffix array versus inverted index, summary), Exercise Sheet 10 (your project idea), Exercise Sheet 11 (your proposal), Exercise Sheet 12 (revised proposal + presentation guidelines), Feedback Form for the Presentations.