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/