View publication
| Title | Indexing Variable Length Substrings for Exact and Approximate Matching |
| Authors | Gonzalo Navarro, Leena Salmela |
| Publication date | 2009 |
| Abstract | 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. |
| Pages | 214-221 |
| Conference name | International Symposium on String Processing and Information Retrieval |
| Publisher | Springer-Verlag (Berlin/Heidelberg, Germany) |
| Reference URL |
|