<div class="csl-bib-body">
<div class="csl-entry">Kutzelnigg, R. (2008). <i>Random bipartite graphs and their application to cuckoo hashing</i> [Dissertation, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-26312</div>
</div>
Diese Doktorarbeit beschäftigt sich mit der Ermittlung der Eigenschaften spezieller zufälliger Graphen, die in enger Verbindung mit dem Algorithmus Cuckoo Hashing stehen. Dieser weist als besondere Eigenschaft eine konstante Zugriffszeit auf, die im Gegensatz zu herkömmlichen Hashalgorithmen nicht nur im Durchschnitt gilt.<br />Der erste Schwerpunkt der Arbeit ist eine genaue Analyse des mittleren Verhaltens von Cuckoo Hashing. Dazu zählt insbesondere die Wahrscheinlichkeit, dass die Konstruktion der Datenstruktur erfolgreich ist. Es gilt, dass der Aufbau der Hashtabelle asymptotisch fast immer gelingt, so ferne die Auslastung einen festen Wert kleiner als 0.5 nicht überschreitet. Im so genannten "kritischen Fall", der einer Auslastung von 0.5 entspricht, sinkt die Erfolgswahrscheinlichkeit asymptotisch jedoch auf einen Wert von ca. 0.861.<br />Weiters wird eine Schranke für den mittleren Aufwand, der zum Aufbau der Datenstruktur notwendig ist hergeleitet, die linear mit der Größe der Datenstruktur wächst. All diese Untersuchungen basieren auf einer Analyse des so genannten Cuckoo Graphen, welcher ein zufälliger bipartiter Graph ist, dessen Eigenschaften in engem Zusammenhang zur Datenstruktur stehen. Dieser Graph wird mit Hilfe von erzeugenden Funktionen modelliert und anschließend wird durch Verwendung einer (doppelten) Sattelpunktsmethode eine asymptotische Approximation der Koeffizienten ermittelt.<br />Ein weiterer Schwerpunkt liegt in der Untersuchung des Einflusses von Modifikationen der dem Verfahren zu Grunde liegenden Datenstruktur.<br />Insbesondere werden zwei neue Verfahren, "asymmetrisches Cuckoo Hashing" und "vereinfachtes Cuckoo Hashing" genannt, eingeführt. Deren Analyse beruht wiederum auf dem Studium von zufälligen Graphen, die an das jeweilige Verfahren angepasst werden. Die in dieser Arbeit durchgeführte Analyse zeigt, dass der mittlere Aufwand von Such- und Einfügeoperationen durch Verwendung von vereinfachtem Cuckoo Hashing im Vergleich zu allen anderen Varianten sinkt. Verglichen mit herkömmlichen Hashalgorithmen die auf Offener Adressierung basieren, ergibt sich eine Beschleunigung von Suchvorgängen, jedoch steigen die Kosten von Einfügeoperationen.
de
dc.description.abstract
This thesis deals with the analysis of a special kind of random graphs and their application to the analysis of a relatively new hash table data structure called cuckoo hashing. Its main notable feature is, that it provides constant worst case search time. First, we present a precise average case analysis of cuckoo hashing. In particular, we determine the probability that the construction of a cuckoo hash table produces no conflicts. We conclude that the construction is asymptotically almost always successful, if the load factor does not exceed a fixed limit less than 0.5. Moreover, we consider the "critical case", that corresponds to the load factor 0.5, and obtain, that the asymptotic success rate is reduced to approximately 0.861. Furthermore, we give an upper bound for the construction time that is linear in the size of the table. The analysis of the algorithm is based on a generating function approach to the so called Cuckoo Graph, a random bipartite graph that is closely related to the data structure. We apply a double saddle point method to obtain asymptotic results. Second, we analyse the influence on the performance caused by modifications of the underlying structure of the cuckoo hash table. The obtained data structures are named "asymmetric cuckoo hashing'' and "simplified cuckoo hashing''. Again, we provide an average case analysis, that is now based on different random graph models. In particular, our analysis shows, that the expected number of steps of search and insertion operations can be reduced by using the simplified version of cuckoo hashing instead of any other cuckoo hash algorithm.<br />Compared to standard algorithms based on open addressing, we notice that the simplified data structure offers increased performance for search operations, but the expected construction time of the hash table increases.<br />
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Hashing
de
dc.subject
zufällige Graphen
de
dc.subject
zufällige bipartite Graphen
de
dc.subject
Sattelpunktmethode
de
dc.subject
Cuckoo Hashing
de
dc.subject
Offene Adressierung
de
dc.subject
Algorithmen
de
dc.subject
hashing
en
dc.subject
random graphs
en
dc.subject
random bipartite graphs
en
dc.subject
saddle point method
en
dc.subject
cuckoo hashing
en
dc.subject
open addressing
en
dc.subject
algorithms
en
dc.title
Random bipartite graphs and their application to cuckoo hashing
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Reinhard Kutzelnigg
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
dc.contributor.assistant
Heuberger, Clemens
-
tuw.publication.orgunit
E104 - Institut für Diskrete Mathematik und Geometrie
-
dc.type.qualificationlevel
Doctoral
-
dc.identifier.libraryid
AC05039082
-
dc.description.numberOfPages
163
-
dc.identifier.urn
urn:nbn:at:at-ubtuw:1-26312
-
dc.thesistype
Dissertation
de
dc.thesistype
Dissertation
en
dc.rights.identifier
In Copyright
en
dc.rights.identifier
Urheberrechtsschutz
de
tuw.advisor.staffStatus
staff
-
tuw.assistant.staffStatus
external
-
item.openaccessfulltext
Open Access
-
item.openairecristype
http://purl.org/coar/resource_type/c_db06
-
item.grantfulltext
open
-
item.mimetype
application/pdf
-
item.languageiso639-1
en
-
item.openairetype
doctoral thesis
-
item.fulltext
with Fulltext
-
item.cerifentitytype
Publications
-
crisitem.author.dept
E104 - Institut für Diskrete Mathematik und Geometrie