Mixed hypergraphs for linear-time construction of denser hashing-based data structures. - In: SOFSEM 2013: Theory and Practice of Computer Science, (2013), S. 356-368
http://dx.doi.org/10.1007/978-3-642-35843-2_31
Effiziente Algorithmen für grundlegende Graphprobleme. - 169 S. : Ilmenau, Techn. Univ., Masterarbeit, 2013
Die Berechnung der starken Zusammenhangskomponenten eines gerichteten Graphen ist eine wichtige Anwendung der Tiefensuche. Diese Arbeit beschäftigt sich mit bekannten Algorithmen für dieses Problem, die alle lineare Zeit benötigen: Tarjan-Algorithmus, Kosaraju-Sharir-Algorithmus und Cheriyan-Mehlhorn-Gabow-Algorithmus. Modifizierte Versionen werden in dieser Arbeit beschrieben und untersucht. Diese Varianten machen die Algorithmen schneller oder sparen Speicherplatz. Die Verfahren werden experimentell verglichen. Diese Arbeit befasst sich auch mit grundlegenden Graphproblemen für das Durchsuchen von großen Graphen, die nicht in den Hauptspeicher passen. Schließlich werden effiziente externe Algorithmen auf azyklische gerichtete Graphen, deren topologische Sortierung gegeben ist, beschrieben. Diese Algorithmen benutzen den Technik Time-Forward-Processing.
On randomness in Hash functions. - In: 29th International Symposium on Theoretical Aspects of Computer Science, (2012), S. 25-28
In the talk, we shall discuss quality measures for hash functions used in data structures and algorithms, and survey positive and negative results. (This talk is not about cryptographic hash functions.) For the analysis of algorithms involving hash functions, it is often convenient to assume the hash functions used behave fully randomly; in some cases there is no analysis known that avoids this assumption. In practice, one needs to get by with weaker hash functions that can be generated by randomized algorithms. A well-studied range of applications concern realizations of dynamic dictionaries (linear probing, chained hashing, dynamic perfect hashing, cuckoo hashing and its generalizations) or Bloom filters and their variants. A particularly successful and useful means of classification are Carter and Wegman's universal or k-wise independent classes, introduced in 1977. A natural and widely used approach to analyzing an algorithm involving hash functions is to show that it works if a sufficiently strong universal class of hash functions is used, and to substitute one of the known constructions of such classes. This invites research into the question of just how much independence in the hash functions is necessary for an algorithm to work. Some recent analyses that gave impossibility results constructed rather artificial classes that would not work; other results pointed out natural, widely used hash classes that would not work in a particular application. Only recently it was shown that under certain assumptions on some entropy present in the set of keys even 2-wise independent hash classes will lead to strong randomness properties in the hash values. The negative results show that these results may not be taken as justification for using weak hash classes indiscriminately, in particular for key sets with structure. When stronger independence properties are needed for a theoretical analysis, one may resort to classic constructions. Only in 2003 it was found out how full randomness can be simulated using only linear space overhead (which is optimal). The "split-and-share" approach can be used to justify the full randomness assumption in some situations in which full randomness is needed for the analysis to go through, like in many applications involving multiple hash functions (e.g., generalized versions of cuckoo hashing with multiple hash functions or larger bucket sizes, load balancing, Bloom filters and variants, or minimal perfect hash function constructions). For practice, efficiency considerations beyond constant factors are important. It is not hard to construct very efficient 2-wise independent classes. Using k-wise independent classes for constant k bigger than 3 has become feasible in practice only by new constructions involving tabulation. This goes together well with the quite new result that linear probing works with 5-independent hash functions. Recent developments suggest that the classification of hash function constructions by their degree of independence alone may not be adequate in some cases. Thus, one may want to analyze the behavior of specific hash classes in specific applications, circumventing the concept of k-wise independence. Several such results were recently achieved concerning hash functions that utilize tabulation. In particular if the analysis of the application involves using randomness properties in graphs and hypergraphs (generalized cuckoo hashing, also in the version with a "stash", or load balancing), a hash class combining k-wise independence with tabulation has turned out to be very powerful.
http://dx.doi.org/10.4230/LIPIcs.STACS.2012.25
Mixing strategies in data compression. - In: Data Compression Conference (DCC), 2012, ISBN 978-1-4673-0715-4, (2012), S. 337-346
We propose geometric weighting as a novel method to combine multiple models in data compression. Our results reveal the rationale behind PAQ-weighting and generalize it to a non-binary alphabet. Based on a similar technique we present a new, generic linear mixture technique. All novel mixture techniques rely on given weight vectors. We consider the problem of finding optimal weights and show that the weight optimization leads to a strictly convex (and thus, good-natured) optimization problem. Finally, an experimental evaluation compares the two presented mixture techniques for a binary alphabet. The results indicate that geometric weighting is superior to linear weighting.
http://dx.doi.org/10.1109/DCC.2012.40
Moderne Verfahren der Routenplanung. - 73 S. : Ilmenau, Techn. Univ., Bachelor-Arbeit, 2012
Durch die Verfügbarkeit von detaillierten Straßendaten in digitaler Form ist die Bedeutung der Routenplanung in den letzten Jahren erheblich gestiegen. Neben dem genaueren Datenmaterial ermöglichen schnellere, auf Straßengraphen spezialisierte Algorithmen in Kombination mit moderner Hardware neue Anwendungsmöglichkeiten. In dieser Arbeit werden mehrere Verfahren vorgestellt, welche zu den derzeit schnellsten Algorithmen zur Wegfindung in Straßengraphen zählen. Mit unserer Implementierung werden die Eigenschaften dieser Algorithmen in Experimenten untersucht. Untersucht werden die Algorithmen PHAST, ContractionHierarchies und HubLabeling.
Explicit and efficient hash families suffice for cuckoo hashing with a stash. - In: Algorithms – ESA 2012, (2012), S. 108-120
http://dx.doi.org/10.1007/978-3-642-33090-2_11
Neue effiziente Versionen des "Lovász Local Lemma (LLL)". - 155 S. : Ilmenau, Techn. Univ., Masterarbeit, 2012
1975 formulierten Erdös und Lovász das Lovász Local Lemma (LLL). Dieses gibt lokale Bedingungen an, die jedes Ereignis einer Menge erfüllen muss, damit mit positiver Wahrscheinlichkeit kein Ereignis dieser Menge eintritt. Das LLL kann verwendet werden, um Existenzbeweise mit der probabilistischen Methode zu führen, beispielsweise um die Existenz erfüllender Belegungen für bestimmte KNF-Formeln zu zeigen. 1991 demonstrierte Beck erstmals, dass es auch eine konstruktive Variante des LLL unter etwas stärkeren Bedingungen gibt. 2010 gelang es Moser und Tardos, einen konstruktiven Beweis des LLL mit Hilfe eines einfachen randomisierten Algorithmus anzugeben, durch den die meisten Anwendungen des LLL algorithmisch gemacht werden können. Weiterhin geben Moser und Tardos eine Parallelisierung und eine Derandomisierung ihres Algorithmus an. In der Arbeit werden die Ergebnisse von Moser und Tardos sowie einige genauere Analysen und Verbesserungen der Moser-Tardos-Algorithmen durch andere Autoren vorgestellt. Insbesondere werden die Bedingungen, unter denen algorithmische Versionen des LLL möglich sind, genauer definiert.
Towards optimal degree-distributions for left-perfect matchings in random bipartite graphs, (2012), S. 99-111
http://dx.doi.org/10.1007/978-3-642-30642-6_11
A more reliable greedy heuristic for maximum matchings in sparse random graphs, (2012), S. 148-159
http://dx.doi.org/10.1007/978-3-642-30850-5_14
Analysis of the linear probing variant of cuckoo hashing. - 53 S. Ilmenau : Techn. Univ., Diplomarbeit, 2012
Cuckoo Hashing ist ein Hashingverfahren mit zwei Hashfunktionen, das Zugriffsoperationen im schlechtesten Fall in konstanter Zeit erlaubt. Leider wird dabei nur knapp die halbe Hash-Tabelle ausgenutzt. Eine bekannte Strategie zur Auflösung von Kollisionen ist lineares Sondieren, womit die gesamte Tabelle ausgenutzt werden kann. Allerdings werden Zugriffe mit zunehmender Tabellenauslastung extrem langsam. Wir analysieren den Platzverbrauch einer Cuckoo-Hashing-Variante, bei der zusätzlich ein Sondierungsschritt pro Hashfunktion erlaubt ist. Im Vergleich zu der Cuckoo-Hashing-Variante, die mind. 3 Hashfunktionen nutzt, eignet sich die Cuckoo-Hashing-Variante mit zusätzlichem Sondierungsschritt eher für Cache-Architekturen. Experimente haben bereits gezeigt, dass bei unserer Cuckoo-Hashing-Variante eine Platzauslastung von ungefähr 96,3% der Hash-Tabelle möglich ist. Wir beweisen (mehr oder weniger formal) eine obere und untere Schranke der Platzauslastung. Wir zeigen, dass unsere Cuckoo-Hashing-Variante mit hoher Wahrscheinlichkeit funktioniert, wenn die Platzauslastung höchstens 82,9% ist. Wir zeigen, dass sie mit hoher Wahrscheinlichkeit nicht funktioniert, wenn die Auslastung mindestens 98,1% beträgt.