Login
Computer Science @ Rochester
Monday, May 10, 2004
11:00 AM
CSB 209
Jeffrey Vitter
Purdue U.
Data, Data Everywhere! Compressed Indexing and Indexed Compression
The online avalanche of text documents and sequence data has made finding information difficult. As a result, efficient indexing of such data is critical. We present the first text index that provably takes about the same space occupied by the text in compressed format, provides fast mechanisms for general string matching, and does not require access to the original uncompressed text.

In particular, for a text of n symbols from alphabet e, we develop a data structure called the compressed suffix array that uses just nHh + O(n(log lg n) / log|(| n) bits while retaining full text indexing functionality, such as searching for patterns in time linear in the pattern length plus a polylogarithmic term in n. The term Hh ( log2 |(| denotes the hth-order empirical entropy of the text, which means that our index is nearly optimal in space apart from lower-order terms, achieving the empirical entropy of the text (with multiplicative constant 1). Our approach is also self-indexing, which means that the original text can be discarded and recovered in a random access manner from the index itself.

This work was done jointly with Ankur Gupta and Roberto Grossi.