This thesis concerns dictionaries and related data structures that rely on providing several random possibilities for storing each key. Imagine information on a set S of m = |S| keys should be stored in n memory locations, indexed by [n] = {1,…,n}. Each object x [ELEMENT OF] S is assigned a small set...
This report documents the program and the topics discussed of the 4-day Dagstuhl Seminar 17181 “Theory and Applications of Hashing”, which took place May 1–5, 2017. Four long and eighteen short talks covered a wide and diverse range of topics within the theme of the workshop. The program left sufficient...
Im Zuge der stetigen Weiterentwicklung moderner Technik wächst die Menge an
zu verarbeitenden Daten.Es gilt diese Daten zu verwalten, zu übertragen und
zu speichern.Dafür ist Datenkompression unerlässlich.Gemessen an
empirischen Kompressionsraten zählen Statistische
Datenkompressionsalgorithmen...
In dieser Dissertation beschäftigen wir uns mit mehreren Problemen in
gerichteten Graphen. Zuerst betrachten wir das Problem der Berechnung der
$2$-fach knotenzusammenhängenden Komponenten in gerichteten Graphen. Wir
präsentieren einen neuen Algorithmus zur Lösung dieses Problems in Zeit
$O(nm)$...
Wir betrachten randomisierte Algorithmen, die bei Eingabe einer Menge S von
n Schlüsseln aus einem Universum U,oder einer Menge von n
Schlüssel-Wert-Paaren eine Datenstruktur für eine der folgenden Aufgaben
bauen.Bei Aufruf der Operation lookup für einen Schlüssel x aus U: *
Entscheide, ob x Element...
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...
Saarbrücken/Wadern: Schloss Dagstuhl - Leibniz-Center for Informatics, 2012-02
In der Dissertation werden strukturelle Probleme in
YaosKommunikationsmodell untersucht, die sich thematisch dreiBereichen
dieses Gebietes zuordnen lassen:Der erste Teil der Arbeit beschäftigt sich
mit dem fundamentalenProblem der Herleitung unterer Schranken für die
randomisierteKommunikationskomplexität....
The contribution of this thesis is a mathematical analysis a high
performance hashing scheme called cuckoo hashing when combined with two very simple and efficient classes of functions that we refer to as the multiplicative class and the linear class, respectively. We prove that cuckoo hashing tends...
We analyze a simple random process in which a token is moved in the interval $A={0,dots,n$: Fix a probability distribution $mu$ over ${1,dots,n$. Initially, the token is placed in a random position in $A$. In round $t$, a random value $d$ is chosen according to $mu$. If the token is in position $ageq...