We investigate the problem of maintaining the arc labels in the suffixtree data structure when it undergoes string insertions and deletions. In current literature, this problem is solved either by a simple accounting strategy to obtain amortized bounds or by a periodical suffix tree reconstruction to obtain worst-case bounds (according to a global rebuilding technique). Unfortunately, the former approach is simple and space-efficient at the cost of attaining amortized bounds for the single update; the latter is space-consuming in practice because it needs to keep two extra suffix tree copies. In this paper, we obtain a simple real-time algorithm that achieves worst-case bounds and only requires small additional space (i.e., a bi-directional pointer per suffix tree label). We analyze it by introducing a combinatorial coloring problem on the suffix tree arcs.
A Note on Updating Suffix Tree Labels / P., Ferragina; R., Grossi; Montangero, Manuela. - STAMPA. - LNCS 1203(1997), pp. 181-192. ((Intervento presentato al convegno 3rd Italian Conference on Algorithms and Complexity, CIAC 1997 tenutosi a UNIV ROME LA SAPIENZA, ROME, ITALY nel 12 March 1997 through 14 March 1997.
Data di pubblicazione: | 1997 | |
Titolo: | A Note on Updating Suffix Tree Labels | |
Autore/i: | P., Ferragina; R., Grossi; Montangero, Manuela | |
Autore/i UNIMORE: | ||
Codice identificativo Scopus: | 2-s2.0-80052964072 | |
Codice identificativo ISI: | WOS:000071536300017 | |
Nome del convegno: | 3rd Italian Conference on Algorithms and Complexity, CIAC 1997 | |
Luogo del convegno: | UNIV ROME LA SAPIENZA, ROME, ITALY | |
Data del convegno: | 12 March 1997 through 14 March 1997 | |
Serie: | LECTURE NOTES IN COMPUTER SCIENCE | |
Volume: | LNCS 1203 | |
Pagina iniziale: | 181 | |
Pagina finale: | 192 | |
Citazione: | A Note on Updating Suffix Tree Labels / P., Ferragina; R., Grossi; Montangero, Manuela. - STAMPA. - LNCS 1203(1997), pp. 181-192. ((Intervento presentato al convegno 3rd Italian Conference on Algorithms and Complexity, CIAC 1997 tenutosi a UNIV ROME LA SAPIENZA, ROME, ITALY nel 12 March 1997 through 14 March 1997. | |
Tipologia | Relazione in Atti di Convegno |
File in questo prodotto:
Pubblicazioni consigliate

I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris