Name
Abstract | ||
|---|---|---|
In this paper, we consider fully-online construction of indexing data structures for multiple texts. Let $T = {T_1, ..., T_K}$ be a collection of texts. By fully on-line, we mean that a new character can be appended to any text in $T$ at any time. This is a natural generalization of semi-online construction of indexing data structures for multiple texts in which, after a new character is appended to the $k$th text $T_k$, then its previous texts $T_1, ..., T_{k-1}$ will remain static. Our fully online scenario arises when we index multi-sensor data. We propose fully online algorithms which construct the directed acyclic word graph (DAWG) and the generalized suffix tree (GST) for $T$ in $O(N log \sigma)$ time and $O(N)$ space, where $N$ and $\sigma$ denote the total length of texts in $T$ and the alphabet size, respectively. |
Year | Venue | DocType |
|---|---|---|
2015 | CoRR | Journal |
Volume | Citations | PageRank |
abs/1507.07622 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Takuya Takagi | 1 | 11 | 6.97 |
| Shunsuke Inenaga | 2 | 595 | 79.02 |
| Hiroki Arimura | 3 | 1130 | 92.90 |