KIT | KIT-Bibliothek | Impressum | Datenschutz

External Batched Range Minimum Queries and LCP Construction

Feist, Daniel

This work deals with I/O-optimal suffix array (SA) and longest common prefix (LCP) array construction in external memory. For this purpose, the I/O-optimale DC3 algorithm is enhanced by LCP construction and adapted accordingly to the external memory model. In this context we present a method to construct the required range minimum queries (RMQs) efficiently in external memory. The core of this work is a description and implementation of the resulting external DC3-LCP algorithm using the Stxxl - the C++ Standard Template Library for Extra Large Data Sets. Experimental results based on realistic, real-world instances rounds off this work.

Volltext §
DOI: 10.5445/IR/1000048581
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Publikationsjahr 2013
Sprache Englisch
Identifikator urn:nbn:de:swb:90-485819
KITopen-ID: 1000048581
Verlag Karlsruher Institut für Technologie (KIT)
Umfang 35 S.
Art der Arbeit Abschlussarbeit - Bachelor
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page