Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

On Constructing Suffix Arrays in External Memory

MPG-Autoren
/persons/resource/persons44266

Crauser,  Andreas
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44412

Ferragina,  Paolo
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte in PuRe verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Crauser, A., & Ferragina, P. (1999). On Constructing Suffix Arrays in External Memory. In J. Nesetril (Ed.), Proceedings of the 7th Annual European Symposium on Algorithms (ESA-99) (pp. 224-235). Berlin: Springer.


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-000F-35E5-A
Zusammenfassung
The construction of full-text indexes on very large text collections is nowadays a hot problem. The suffix array~\cite{Manber-Myers} is one of the most attractive full-text indexing data structures due to its simplicity, space efficiency and powerful/fast search operations supported. In this paper we analyze theoretically and experimentally, the I/O-complexity and the working space of six algorithms for constructing large suffix arrays. Additionally, we design a new external-memory algorithm that follows the basic philosophy underlying the algorithm in~\cite{book-info} but in a significantly different manner, thus combining its good practical qualities with efficient worst-case performances. At the best of our knowledge, this is the first study which provides a wide spectrum of possible approaches to the construction of suffix arrays in external memory, and thus it should be helpful to anyone who is interested in building full-text indexes on very large text collections.