Near-Optimal Space Perfect Hashing Algorithms

**
**

**
Fabiano Botelho,
Nivio Ziviani.
**

**
Wilkerson L. Andrade,
Patricia D. L. Machado.
**

A perfect hash function (PHF) is an injective function that maps keys from a set S to unique values. Since no collisions occur, each key can be retrieved from a hash table with a single probe. A minimal perfect hash function (MPHF) is a PHF with the smallest possible range, that is, the hash table size is exactly the number of keys in S. Differently from other hashing schemes, MPHFs completely avoid the problem of wasted space and wasted time to deal with collisions. The study of perfect hash functions started in the early 80s, when it was proved that the theoretic information lower bound to describe a minimal perfect hash function was approximately 1.44 bits per key. Although the proof indicates that it would be possible to build an algorithm capable of generating optimal functions, no one was able to obtain a practical algorithm that could be used in real applications. Thus, there was a gap between theory and practice. The main result of the thesis filled this gap, lowering the space complexity to represent MPHFs that are useful in practice from O(n log n) to O(n) bits. This allows the use of perfect hashing in applications to which it was not considered a good option. This explicit construction of PHFs is something that the data structures and algorithms community has been looking for since the 1980s. In the context of reactive systems, several conformance testing strategies have been developed based on variations of labeled transition systems (LTS). However, these models are not suitable when the specification uses large or infinite data domains because each value in the data domain is represented as a system state, leading to an explosion of the state space. This problem is even bigger at interruption testing level, where the possible number of combinations of interruptions at different points of an execution path is huge. Symbolic transition systems (STS) are models where variables and parameters are explicitly represented and these information are treated in a symbolic way. In this work, we present an approach to modeling and testing from STS models of reactive systems with interruptions, and thus make possible the automatic test generation through direct manipulation of high-level specifications avoiding state space enumeration.

http://www.lbd.dcc.ufmg.br/colecoes/ctd/2009/005.pdf

Biblioteca Digital Brasileira de Computação - Contato: bdbcomp@lbd.dcc.ufmg.br