Publications

Basierend auf der Arbeit [TCS '04] von Kristiansen und Niggl stellen Niggl und Wunderlich in ihrer Arbeit [SIAM '06] eine Methode M zur statischen Analyse des Ressourcenbedarfs von imperativen Programmen vor, die aus beliebigen Basisanweisungen (auf beliebigen Datenstrukturen) mittels Sequenzierung, Konditionalen und FOR-Schleifen gebildet werden. Diese Methode ermöglicht unter anderem die Zertifizierung von "polynomiell größenbeschränkten" Programmen; dies sind solche imperative Programme P mit Variablen X_1, ... , X_n, für welche mit i=1,..., n gilt: Nach der Ausführung von P ist die Größe des in X_i gespeicherten Datenobjekts beschränkt durch ein Polynom in den Größen der initialen Belegung von X_1,...,X_n. Ferner wurde gezeigt, dass die zertifizierten "String-Programme" genau die polynomialzeitberechenbaren Funktionen (FP) berechnen. Diese Diplomarbeit untersucht nun Modifikationen an M sowie an der in Mehlers Diplomarbeit [TU-Ilmenau '05] vorgestellten Methode M', eine um den "additiven Fall" verallgemeinerte Verfeinerung von M, mit dem Ziel, die Klasse der zertifierten Progamme gegenüber M und M' signifikant zu erweitern. Ausgangspunkt der Überlegungen ist die Arbeit [CiE '05] von Kristiansen und Jones. Dort wird eine weitere Zertifizierungsmethode vorgestellt, welche insbesondere wachstumsneutrale zyklische Zuweisungsfolgen zulässt, die sowohl eine Zertifizierung durch M, als auch durch M' verhindern. In dieser Diplomarbeit wird gezeigt, dass eine verfeinerte Analyse des potentiellen gegenseitigen Einflusses von Variablen erlaubt, Programme mit wachstumsneutralgen Zuweisungszyklen durch eine Modifikation M'' von M zu zertifizieren. Ferner wird gezeigt, wie sich die duch M' realisierten Modifikationen in die verfeinerte Analyse integrieren lassen. Grundlegend für die verfeinerte Analyse ist eine genaue Untersuchung und Charakterisierung des M zugrundeliegenden Matrizenkalküls. Als Ergebnis der genauen Charakterisierung der verwendeten Operatoren wird erstmalig ein effizienter Algortihmus, Closure, vorgestellt, der aus einem gegebenen Zertifikat Y für ein Programm in n Variablen die j-te Spalte der transitiven Hülle von Y in Zeit O(nџ log n) und mit Platzbedarf O(nø) berechnet. Closure basiert wesentlich auf teilweise neuen graphentheoretischen Analysen und liefert erstmalig den Nachweis, dass sowohl M und M' als auch M'' effiziente Zertifizierungsverfahren darstellen.

Der standard Bloom-Filter, 1970 von Burton H. Bloom entworfen, ist eine einfache probabilistische Datenstruktur zur Berechnung der charakteristischen Funktion einer Menge. Er erlaubt eine kleine Falsch-Positiv-Rate, ermöglicht aber eine hohe Speichereffizienz. In den letzten Jahren haben Bloom-Filter stark an Popularität gewonnen und die Original-Datenstruktur wurde auf vielfältige Weise angepasst und verändert. Die Varianten lassen sich in drei Kategorien unterteilen: Bloom-Filter für Mengen, Counting-Bloom-Filter für Multimengen und Bloomier-Filter für Wörterbücher. Diese Diplomarbeit behandelt neuere Bloom-Filter-Varianten mit Schwerpunkt auf der Analyse und dem Vergleich ihrer Fehlerwahrscheinlichkeiten. Dafür wurde die relevante Literatur aufgearbeitet und einer einheitlichen mathematischen Darstellung unterzogen. Vorteile einzelner Varianten stellten sich als stark anwendungsspezifisch heraus. Beispielsweise erreichten Datenstrukturen die auf Fingerprints und der d-left-Hashing-Technik basieren erst ab einer bestimmten Größe eine kleinere Falsch-Positiv-Rate als die Standard-Konstruktion.

We study a particular aspect of the balanced allocation paradigm (also known as the "two-choices paradigm"): constant sized bins, packed as tightly as possible. Let d >= 1 be fixed, and assume there are m bins of capacity d each. To each of n <= d*m$ balls two possible bins are assigned at random. How close can dm/n = 1 + epsilon be to 1 so that with high probability each ball can be put into one of the two bins assigned to it, without any bin overflowing? We show that epsilon > (2/e)^(d-1) is sufficient. If a new ball arrives with two new randomly assigned bins, we wish to rearrange some of the balls already present in order to accommodate the new ball. We show that on average it takes constant time to rearrange the balls to achieve this, for epsilon > beta^d, for some constant beta < 1. An alternative way to describe the problem is in data structure language. Generalizing cuckoo hashing (Pagh and Rodler, 2004), we consider a hash table with m positions, each representing a bucket of capacity d >= 1. Keys are assigned to buckets by two fully random hash functions. How many keys can be placed in these bins, if key x may go to bin h_1(x) or to bin h_2(x)? We obtain an implementation of a dictionary that accommodates n keys in m = (1+epsilon)n/d buckets of size d = O(log(1/epsilon)), so that key x resides in bucket h_1(x) or h_2(x). For a lookup operation, only two hash functions have to be evaluated and two segments of d contiguous memory cells have to be inspected. If d >= 1 + 3.26 * ln(1/epsilon), a static arrangement exists with high probability. If d >= 16 * \ln(1/epsilon), a dynamic version of the dictionary exists so that the expected time for inserting a new key is log(1/epsilon)^(O(log log(1/epsilon))).