Conference Paper
Title: Blooming Trees for Minimal Perfect Hashing
Authors: Gianni Antichi, Domenico Ficara, Stefano Giordano, Gregorio Procissi, Fabio Vitucci

Conference: Globecom 2008, 30 November - 4 December 2008, New Orleans, USA
Abstract: Hash tables are used in many networking applications, such as lookup and packet classification. But the issue of collisions resolution makes their use slow and not suitable for fast operations. Therefore, perfect hash functions have been introduced to make the hashing  mechanism more efficient. In particular, a minimal perfect hash function is a function that maps a set of n keys into a set of n integer numbers without collisions. In literature, there are many schemes to construct a minimal perfect hash function, either based on mathematical properties of polynomials or on graph
theory. This paper proposes a new scheme which shows remarkable results in terms of space consumption and processing speed. It is based on an
alternative to Bloom Filters and requires about 4 bits per key and 12:8 seconds to construct a MPHF with 3:8_109 elements.