Random bipartite graphs and their application to cuckoo hashing

Abstract

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.

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 />