Nowadays textual databases are among the most rapidly growing collections of data. Some of
these collections contain a new type of data that differs from classical numerical or textual
data. These are long sequences of symbols not divided into well-separated small tokens
(words). The most prominent among such collections are databases of biological sequences which
are experiencing today an unprecedented growth rate. Starting in 2008 the 1000 Genomes Project
has been launched with the ultimate goal of collecting sequences of additional 1 500 Human
genomes 500 each of European African and East Asian origin. This will produce an extensive
catalog of Human genetic variations. The size of just the raw sequences in this catalog would
be about 5 terabytes. Querying strings without well-separated tokens poses a different set of
challenges typically addressed by building full-text indexes which provide effective
structures to index all the substrings of the given strings. Since full-text indexes occupy
more space than the raw data it is often necessary to use disk space for their construction.
However until recently the construction of full-text indexes in secondary storage was
considered impractical due to excessive I O costs. Despite this algorithms developed in the
last decade demonstrated that efficient external construction of full-text indexes is indeed
possible. This book is about large-scale construction and usage of full-text indexes. We focus
mainly on suffix trees and show efficient algorithms that can convert suffix trees to other
kinds of full-text indexes and vice versa. There are four parts in this book. They are a mix of
string searching theory with the reality of external memory constraints. The first part
introduces general concepts of full-text indexes and shows the relationships between them. The
second part presents the first series of external-memory construction algorithms that can
handle the construction of full-text indexes for moderately large strings in the order of few
gigabytes. The third part presents algorithms that scale for very large strings. The final part
examines queries that can be facilitated by disk-resident full-text indexes. Table of Contents:
Structures for Indexing Substrings External Construction of Suffix Trees Scaling Up: When
the Input Exceeds the Main Memory Queries for Disk-based Indexes Conclusions and Open
Problems
