Hybrid indexing revisited

Hybrid indexing is a recent approach to text indexing that allows the space-usage of conventional text indexes (e.g., su x trees, su x arrays, FM-indexes) to scale well with the text size, n, when z, the size of the Lempel-Ziv parsing of the text, is small relative to n. The price for this improved scalability is that an upper bound M on the pattern length that can be searched for must be declared at index construction time. Because the size of the resulting index contains an O(Mz) term, M must be kept reasonably small, though it has been shown that M ? 100 leads to acceptable performance in some genomic applications. However, despite its promise, the practical performance of hybrid indexing relative to other compressed index data structures is poorly understood. This paper addresses that need, detailing experiments that show hybrid indexing — when carefully implemented — to be significantly smaller and faster than alternative approaches on a broad range of data of di erent levels of compressibility. We also describe practical extensions to hybrid indexing that obviate the restriction on M, supporting search for patterns of arbitrary length.