In this paper, we describe a strategy of using compressedbitmap indices to speed up queries on both numerical data and textdocuments. By using an efficient compression algorithm, these compressedbitmap indices are compact even for indices with millions of distinctterms. Moreover, bitmap indices can be used very efficiently to answerBoolean queries over text documents involving multiple query terms.Existing inverted indices for text searches are usually inefficient forcorpora with a very large number of terms as well as for queriesinvolving a large number of hits. We demonstrate that our compressedbitmap index technology overcomes both of those short-comings. In aperformance comparison against a commonly used database system, ourindices answer queries 30 times faster on average. To provide full SQLsupport, we integrated our indexing software, called FastBit, withMonetDB. The integrated system MonetDB/FastBit provides not onlyefficient searches on a single table as FastBit does, but also answersjoin queries efficiently. Furthermore, MonetDB/FastBit also provides avery efficient retrieval mechanism of result records.

• Preface
• Acknowledgments --

• 1. Structures for indexing substrings
• 1.1 Indexing substrings
• 1.2 Suffix array
• 1.3 Suffix trie
• 1.4 Suffix tree
• 1.5 Representation of a suffix tree
• 1.6 Possible solutions to the memory problem
• 1.6.1 Index compression
• 1.6.2 Using disk space
• 1.7 Summary
• 1.8 Bibliographic notes --

• 2. External construction of suffix trees
• 2.1 Transformation algorithms
• 2.2 Brute-force algorithms
• 2.3 Algorithms based on suffix-links
• 2.3.1 The Ukkonen algorithm
• 2.3.2 Distributed and paged suffix trees
• 2.4 Disk-optimized algorithms
• 2.4.1 The top down algorithm
• 2.4.2 The partition-and-merge algorithm
• 2.4.3 The merge sort algorithm
• 2.5 Summary
• 2.6 Bibliographic notes --

• 3. Scaling up:when the input exceeds the main memory
• 3.1 The wavefront algorithm
• 3.2 The B2ST algorithm
• 3.3 Summary
• 3.4 Bibliographic notes --

• 4. Queries for disk-based indexes
• 4.1 Index layouts
• 4.1.1 Partitioning by prefix
• 4.1.2 Partitioning by intervals
• 4.1.3 String B-tree
• 4.2 Pattern matching with disk-based indexes
• 4.2.1 Exact pattern matching
• 4.2.2 Matching all substrings of a query string
• 4.2.3 Approximate pattern matching
• 4.3 Repeating and unique substrings
• 4.3.1 Maximal repeats
• 4.3.2 Common and unique substrings
• 4.4 Summary
• 4.5 Bibliographic notes --

• 5. Conclusions and open problems
• 5.1 Need for better construction algorithms
• 5.2 Need for better query algorithms --

• Bibliography
• Authors' biographies.

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.

Many large collections of full-text documents are currently stored in machine-readable form and processed automatically in various ways. These collections may include different types of documents, such as messages, research articles, and books, and the subject matter may vary widely. To process such collections, robust text analysis methods must be used, capable of handling materials in arbitrary subject areas, and flexible access must be provided to texts and text excerpts of varying size.
In this study, global text comparison methods are used to identify similarities between text elements, followed by local context-checking operations that resolve ambiguities and distinguish superficially similar texts from texts that actually cover identical topics. A linked text structure is then created that relates similar texts at various levels of detail. In particular, text links are available for full texts, as well as text sections, paragraphs, and sentence groups. The linked structures are usable to identify important text packages, to traverse texts selectively both within particular documents and between documents, and to provide flexible text access to large text collections in response to various kinds of user needs. An automated 29-volume encyclopedia is used as an example to illustrate the text accessing and traversal operations.