Abstract | ||
---|---|---|
We present a novel compressed dynamic self-index for highly repetitive text collections. Signature encoding, an existing self-index of this type, has a large disadvantage of slow pattern search for short patterns. We obtain faster pattern search by leveraging the idea behind a truncated suffix tree (TST) to develop the first compressed dynamic self-index, called the TST-index, that supports not only fast pattern search but also dynamic update operations for highly repetitive texts. Experiments with a benchmark dataset show that the pattern search performance of the TST-index is significantly improved. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1109/DCC.2018.00037 | 2018 Data Compression Conference |
Keywords | Field | DocType |
Compressed index,Dynamic index | Data structure,Computer science,Theoretical computer science,Suffix tree,Benchmark (computing),Pattern search,Encoding (memory) | Conference |
ISSN | ISBN | Citations |
1068-0314 | 978-1-5386-4884-1 | 0 |
PageRank | References | Authors |
0.34 | 10 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Takaaki Nishimoto | 1 | 23 | 3.54 |
Yoshimasa Takabatake | 2 | 29 | 7.27 |
Yasuo Tabei | 3 | 215 | 19.46 |