http://www.tu-ilmenau.de

FG Komplexitätstheorie und Effiziente Algorithmen

Ansprechpartner

Univ.-Prof. Dr. Martin Dietzfelbinger

Fachgebietsleiter

Telefon +49 (0)3677 69 2656

E-Mail senden

INHALTE

## Modern Hashing

Associated project within the
DFG Priority Program 1307 "Algorithm Engineering"

Funding: German National Science Foundation (DFG)

1st project phase: 01/2008-12/2009
2nd project phase: 03/2010-02/2013

### Introduction:

The "multiple-choice-paradigm" proofed to be very efficient in distributing objects among a set of locations as evenly as possible ("ballanced allocation"). For example consider the classical problem of throwing n balls into n bins. If each ball chooses its position uniformly at random then the maximum load is about ln(n)/ln(ln(n)) (with high probability). But if each ball has k>=2 randomly chosen positions and we place the ball in the least loaded bin then the maximum load reduces to roughly ln(ln(n))/ln(k) (with high probability).

Translated in terms of "hashing" we have a set S of keys from some universe and each key from S gets a small number k of easy calculatable hash values (indices) from some range R. This approach is used to build fundamental data structures like

• dictionary
• bloom filter
• (minimal) perfect hash function

with constant access time (essentially dependent of k) and small space usage (essentially dependent of |R|).

### Objectives:

1. Fore some applications of the multiple-choice-paradigm it is assumed that fully random hash functions are available. We want to investigate applications and limits of a new algorithmic approach, called "split-and-share", that can help to justify this assumption.
2. Against the background of efficient implementation of data structures we want to study the effect of applying simple and fast hash functions (with limited randomness) to the multiple-choice-paradigm.
3. In general we want to improve methods of analysis to get a deeper understanding of the paradigm and get to space optimal data structures.

### Contact:

Prof. Martin Dietzfelbinger

### Researcher:

Prof. Martin Dietzfelbinger

#### scientific staff - project funding

Dipl.-Inf. Michael Rink
B. Sc. Hendrik Peilke (master student)

#### scientific staff - state funding

Dr. Ulf Schellbach
Dipl.-Inf. Martin Aumüller

### Publications:

#### 2010

Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh, Michael Rink
Tight Thresholds for Cuckoo Hashing via XORSAT
ICALP (1) 2010: 213-225

#### 2009

Martin Dietzfelbinger, Ulf Schellbach
On Risks of Using Cuckoo Hashing with Simple Universal Hash Classes
SODA 2009: 795-804

Martin Dietzfelbinger, Ulf Schellbach
Weaknesses of Cuckoo Hashing with a Simple Universal Hash Class:The Case of Large Universes
SOFSEM 2009: 217-228

Martin Dietzfelbinger, Michael Rink
Applications of a Splitting Trick
ICALP (1) 2009: 354-365

Martin Aumüller, Martin Dietzfelbinger, Michael Rink
Experimental Variations of a Theoretically Good Retrieval Data Structure
ESA 2009: 742-751

Djamal Belazzougui, Fabiano C. Botelho, Martin Dietzfelbinger
Hash, Displace, and Compress
ESA 2009: 682-693

Martin Dietzfelbinger, Stefan Edelkamp
Perfect Hashing for State Spaces in BDD Representation
KI 2009: 33-40

#### 2008

Martin Dietzfelbinger, Rasmus Pagh
Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract)
ICALP (1) 2008: 385-396