Logo Universität Bremen


Universität Bremen - Fachbereich 3 - Informatik


Startseite Detail

Perfect Hashing in Theory and Practice

Datum: 04.11.2009

Ort: Cartesium Rotunde

Vortragende(r): Dr. Stefan Edelkamp (Universität Bremen)


A perfect hash function for a set S is a hash function that maps distinct elements in S to distinct integers, with no collisions. A perfect hash function with values in a limited range can be used for efficient lookup operations, by placing keys from S (or other associated values) in a table indexed by the output of the function. A minimal perfect hash function is a perfect hash function that maps n keys to [1..n]. It has been proven that any minimal perfect hash scheme requires at least 1.44 bits/key. However, the smallest currently use around 2.5 bits/key. Some of these space-efficient perfect hash functions have been implemented. A apperent alternative to perfect hashing with dynamic updates is cuckoo hashing. In the talk we will introduce the concept of (minimal) perfect hashing and show how it can be applied to solve large model checking problems semi-externally. We also address the problem of designing suitable minimal perfect hash functions for solving single-agent puzzles and two-player games space-efficiently. Last, but not least, we derive a minimal perfect hash function for state sets represented in form of a binary decision diagram (BDD).


Stefan Edelkamp is with the Center for Computing and Communication Technology (TZI) at the Universität Bremen since 2008. Prior to his stay in Bremen he has been leading young research groups in Freiburg and Dortmund, with one of his PhDs graduating Summa Cum Laude. Stefan Edelkamp is an internationally acting researcher; according to DBLP he has published more than 80 archived papers and three books in the areas of data structures, model checking and AI, being ranked second on German AI venues. He is on the editorial board of JAIR and steering committee member of MOCHART and SPIN. He will organize a Dagstuhl Seminar on Graph Search Enginering end of November, AAAI-10's students abstract and poster session in Atlanta, and the International Conference on Automated Planning and Scheduling Systems (ICAPS-11) in Freiburg. Stefan Edelkamp is a good programmer. He likely has implemented the world's fastest sequential sorting algorithm (weak-heap sort) and priority queue data structure (rank-relaxed weak queue). Moreover, he is acting world champion in cost-optimal deterministic and non-deterministic AI planning. Stefan Edelkamp is in the lead of several DFG projects, including topics on directed, parallel, and external model checking, general game playing & algorithm engineering, and currently in charge of coordinating the FIDES BMBF project that integrates AI methods for improved intrusion detection in computer networks.