Compressed Text Indexing and Range Searching
Yu-Feng Chien, Wing-Kai Hon, Rahul Shah, Jeffrey Scott Vitter · Purdue e-Pubs (Purdue University System) · 2006
We introduce two transformations Text2Points and Points2Text that, respectively, convert text to points in space and vice-versa. With these transformations, data structural problems in pattern matching and geometric range searching can be linked. We show strong connections between space versus query time trade-offs in these fields. Thus, the results in range searching can be applied to compressed indexing and vice versa. In particular, we show that for a given equivalent space, pattern matching queries can be done using 2-D range searching and vice-versa with query times within a factor of O(1ogn) of each other. This two-way connection enables us not only to design new data structures for compressed text indexing, but also to derive new lower bounds. For compressed text indexing, we propose alternative data structures based on our Text2Points transform and Csided orthogonal query structures in 2-D. Currently, all proposed compressed text indexes are based on the Burrows-Wheeler transform (BWT) or its inverse [16,17,20,22,42]. We observe that our Text2Points transform is related to BWT on blocked text, and hence we also call it geometric BWT. With this variant, we solve some well-known open problems in this area of compressed text indexing. In particular, we present the first external memory results for compressed text indexing. We give the first compressed data structures for position-restricted pattern matching [27,34]. We also show lower bounds for these problems and for the problem of text indexing in general. These are the first known lower bounds (hardness results) in this area.