Powered by MyCoRe


Titel:Platzeffiziente Hashverfahren mit garantierter konstanter Zugriffszeit
Autor:Dr. rer. nat. Weidling, Christoph [Autor]
Dateien:
[Dateien anzeigen]ASCII Text, Adobe PDF, Unbekannter Dateityp
[Details]6,47 MB in 34 Dateien
[ZIP-Datei erzeugen][PlugIn/Viewer Download]
Dateien vom 20.12.2004 / geändert 04.05.2006
URL für Lesezeichen:http://www.db-thueringen.de/servlets/DocumentServlet?id=2431
URN (NBN):urn:nbn:de:gbv:ilm1-2004000134
Kollektion:Dissertationen/Habilitationen
Status:Dokument veröffentlicht
Sprache:Deutsch
Dokumententyp:Dissertation
Medientyp:Text
Beitragende:Univ.-Prof. Dr. Dietzfelbinger, Martin [Gutachter]
Univ.-Prof. Dr. rer.nat. Goerdt, Andreas [Gutachter]
Univ.-Prof. Dr. rer.nat. Sanders, Peter [Gutachter]
Stichwörter:Hash-Algorithmus ; data structures, algorithms, hashing, dictionaries, random graphs, finger prints, dynamic sets
Evaluationstyp:Für die Langzeitarchivierung vorgesehen
Dewey Decimal Classification:000 Informatik, Informationswissenschaft, allgemeine Werke » 000 Informatik, Wissen, Systeme » 004 Datenverarbeitung; Informatik
Andere Dokumente dieser Kategorie
Beschreibungen:Abstract (eng.)

Zusammenfassung:
Wir stellen ein neues Verfahren zur Konstruktion einer minimalen perfekten Hashfunktion (MPHF) und ein neues cachefreundliches dynamisches Wörterbuch vor, beschreiben die neuen Verfahren algorithmisch und analysieren sie hinsichtlich Platzbedarf und Laufzeit. Für die Analyse nehmen wir an, dass die in den Verfahren benutzten Hashfunktionen volle Unabhängigkeit gewährleisten. Schließlich werden wir jeweils experimentelle Resultate angeben und interpretieren. Wir zeigen, dass man eine minimale perfekte Hashfunktion für n Schlüssel mit einem Platzbedarf von 0.93n Wörtern in erwarteter Zeit O(n) realisieren kann. Zur Auswertung der MPHF werden 2 Hashfunktionen berechnet und zwei Speicherzugriffe durchgeführt. Unser dynamisches Wörterbuch benötigt (1+epsilon)n Platz für ein beliebiges epsilon > 0. Bei der Suche müssen 2 Hashfunktionen ausgewertet und 2d Speicherzellen inspiziert werden, die in zwei zusammenhängenden Speicherbereichen liegen, wobei d >= 1+3.26 ln(1/epsilon). Wir können zeigen, dass für d >= 90.1 ln(1/epsilon) die erwartete Einfügezeit für einen neuen Schlüssel konstant ist. Am Ende werden wir zeigen, wie man dynamisches Hashing mit Zeichenketten cachefreundlich realisieren kann.
Hochschule/Fachbereich:Technische Universität Ilmenau » Fakultät für Informatik und Automatisierung
Dokument erstellt am: 20.12.2004
Dateien geändert am: 04.05.2006
Datum der Promotion: 04.10.2004