The seminar
will focus mainly on indexing text and compressed text. In the last third we
will cover some papers on simplex range searching.
In the first part on strings we will use two main references as well as several recent papers. The two main references are
1. Algorithms on Strings, Trees and Sequences / D. Gusfield
2. Compressed full-text indexes / G.
Navarro and V. Makinen
In the second part some of the material is in the chapter
of the classical book on computation geometry by de Berg, van Kreveld, Overmars, and
Schwarzkopf: Computational
geometry: Algorithms and Applications.
Tentative
schedule
Indexing text
· The algorithm of McCreight for constructing the suffix tree. The original paper is A Space-Economical Suffix Tree Construction Algorithm / McCreight JACM 23, 1976. Presentation by Aviv Avitan.
·
Udi Manber and Gene Myers (1991). "Suffix arrays: a new
method for on-line string searches".
·
Rank and select
in binary and general sequences. Based on Sections 6.1, 6.2, and 6.3 from ref
(2) above. Presentation
by Omer Cohen
·
Introduction to the Burrows-Wheeler transform
and compression algorithms based on it. Here are three good sources. 1) The original technical report of Burrows and
Wheeler: A
block-sorting lossless data compression algorithm. 2) A paper by Fenwick: Burrows
Wheeler Compression: Principles and Reflections. 3) A paper by Landau, Verbin, and myself: A
Simpler Analysis of Burrows-Wheeler Based Compression. Presentation by Inna Katz
·
Compressed suffix arrays. Sections 7 and 8
of ref (2) above and the original papers mentioned there. In particular this
all started when the first draft of the paper compressed
suffix arrays and suffix trees with applications to text indexing and string
matching by Grossi
and Vitter appeared. Presentation
by Michal Ofir
·
Backwards search and the FM-index. Section
9 of ref (2) above and the original papers mentioned there. The main original
paper here is Indexing compressed text by Ferragina
and Manzini. Presentation by Yuval
Rikover
·
Boosting textual compression in optimal linear time by Ferrangina, Giancarlo, Manzini, Sciortino, 2005. Presentation
by Maor Itzkovitch
Simplex range searching
·
Cutting tree and the cutting lemma. The
proof of the cutting lemma can be found in the book by Matousek:
Lectures
on Discrete Geometry, the rest is in Section 16.3 of the computational
geometry book mentioned above. Presentation
by Amir Mograbi
·
Partition trees. The paper Efficient
partition trees by Matousek and Sections 16.1 and
16.2 of ref (2). Presentation
by Benny Schlesinger and Omer Tavori
·
The paper Reporting points in halfspaces by Matousek.
·
Cutting hyperplanes
for Divide-and-Conquer by Chazelle.