Date: 04 Jan 2010
From: jyrki@diku.dk
Subject: Talk on perfect hashing

Guest lecture: Perfect Hashing in Search Practice
Speaker: Stefan Edelkamp
Time: Tuesday, 5 January 2010 at 13.15–14.15 (1 hour)
Place: 3-1-25

Abstract:

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
effcient 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]. Any minimal perfect hash scheme requires at least 1.44
bits/key.  However, the smallest currently use around 2 bits/key. Some
of these space-efficient perfect hash functions have been implemented.

In the talk we review 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's home page: http://www.tzi.de/~edelkamp
PE-lab's home page: http://www.diku.dk/~jyrki/PE-lab/