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 the 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.

On updating suffix tree labels / P., Ferragina; R., Grossi; Montangero, Manuela. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 201:(1998), pp. 249-262. [10.1016/S0304-3975(97)00243-0]

On updating suffix tree labels

MONTANGERO, Manuela
1998

Abstract

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 the 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.
1998
201
249
262
On updating suffix tree labels / P., Ferragina; R., Grossi; Montangero, Manuela. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 201:(1998), pp. 249-262. [10.1016/S0304-3975(97)00243-0]
P., Ferragina; R., Grossi; Montangero, Manuela
File in questo prodotto:
File Dimensione Formato  
FerraginaGrossiMontangero.pdf

Accesso riservato

Tipologia: Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione 1.04 MB
Formato Adobe PDF
1.04 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Licenza Creative Commons
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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/455363
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 4
social impact