Indexing Variable Length Substrings for Exact and Approximate Matching

Gonzalo Navarro and Leena Salmela

We introduce two new index structures based on the q-gram index. The new structures index substrings of variable length instead of q-grams of fixed length. For both of the new indexes, we present a method based on the suffix tree to efficiently choose the indexed substrings so that each of them occurs almost equally frequently in the text. Our experiments show that the resulting indexes are up to 40% faster than the q-gram index when they use the same space.