Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  On Constructing Suffix Arrays in External Memory

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.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-35E5-A Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-35E7-6
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Crauser, Andreas1, Autor           
Ferragina, Paolo1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010-03-021999
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 518033
Anderer: Local-ID: C1256428004B93B8-98630A327E04E847C1256888004FCB59-Crauser1999
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: Prague, Czech Republic
Start-/Enddatum: 1999

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Proceedings of the 7th Annual European Symposium on Algorithms (ESA-99)
Genre der Quelle: Konferenzband
 Urheber:
Nesetril, Jaroslav, Herausgeber
Affiliations:
-
Ort, Verlag, Ausgabe: Berlin : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 224 - 235 Identifikator: -

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 1643 Artikelnummer: - Start- / Endseite: - Identifikator: -