Please use this identifier to cite or link to this item:
doi:10.22028/D291-25687
Title: | LEDA-SM: External Memory Algorithms and Data Structures in theory and practice |
Author(s): | Crauser, Andreas |
Language: | English |
Year of Publication: | 2001 |
SWD key words: | Peripherer Speicher ; Festplatte ; Algorithmus ; Datenstruktur |
Free key words: | Peripherer Speicher ; Prioritätswarteschlange ; Suffix Array |
DDC notations: | 004 Computer science, internet |
Publikation type: | Dissertation |
Abstract: | Data to be processed has dramatically increased during the last years. Nowadays,
external memory (mostly hard disks) has to be used to store this massive data. Algorithms and data structures that work on external memory have different properties and specialties that distinguish them from algorithms and data structures, developed for the RAM model. In this thesis, we first explain the functionality of external memory,which is realized by disk drives. We then introduce the most important theoretical I/O models. In the main part, we present the C++ class library LEDA-SM. Library LEDA-SM is an extension of the LEDA library towards external memory computation and consists of a collection of algorithms and data structures that are designed to work efficiently in external memory. In the last two chapters, we present new external
memory data structures for external memory priority queues and new external memory construction algorithms for suffix arrays. These new proposals are theoretically analyzed and experimentally tested. All proposals are implemented using the LEDA-SM library. Their efficiency is evaluated by performing a large number of experiments. Die zu verarbeitenden Datenmengen sind in den letzten Jahren dramatisch gestiegen, so daß Externspeicher (in Form von Festplatten) eingesetzt wird, um die Datenmengen zu speichern. Algorithmen und Datenstrukturen, die den Externspeicher benutzen, haben andere algorithmische Anforderungen als eine Vielzahl der bekannten Algorithmen und Datenstrukturen, die für das RAM-Modell entwickelt wurden. Wir geben in dieser Arbeit erst einen Einblick in die Funktionsweise von Externspeicher anhand von Festplatten und erklären die wichtigsten theoretischen Modelle, die zur Analyse von Algorithmen benutzt werden. Weiterhin stellen wir eine neu entwickelte C++ Klassenbibliothek namens LEDA-SM vor. LEDA-SM bietet eine Sammlung von speziellen Externspeicher Algorithmen und Datenstrukturen. Im zweiten Teil entwickeln wir neue Externspeicher-Prioritätswarteschlangen und neue Externspeicher- Konstruktionsalgorithmen für Suffix Arrays. Unsere neuen Verfahren werden theoretisch analysiert, mit Hilfe von LEDA-SM implementiert und anschließend experimentell getestet. |
Link to this record: | urn:nbn:de:bsz:291-scidok-1737 hdl:20.500.11880/25743 http://dx.doi.org/10.22028/D291-25687 |
Advisor: | Kurt Mehlhorn |
Date of oral examination: | 2-Mar-2001 |
Date of registration: | 17-Feb-2004 |
Faculty: | MI - Fakultät für Mathematik und Informatik |
Department: | MI - Informatik |
Collections: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Files for this record:
File | Description | Size | Format | |
---|---|---|---|---|
AndreasCrauser_ProfDrKurtMehlhorn.pdf | 1,03 MB | Adobe PDF | View/Open |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.