Invited Talk:

Near Space-Optimal Perfect Hashing Algorithms

Minimal perfect hash functions are widely used for memory efficient storage and fast retrieval of items from static sets, such as words in natural languages, reserved words in programming languages or interactive systems, universal resource locations (URLs) in web search engines, or item sets in data mining techniques. A perfect hash function (PHF) $ h: U \rightarrow [0,m-1]$ for a key set  $ S$ is a function that maps the keys of $ S$ to unique values. A minimal perfect hash function (MPHF) is a PHF with the smallest range, i.e., $ m=n$. The minimum amount of space to represent a PHF for a given set $ S$ is known to be approximately $ 1.4427n^2/m$ bits, where $ n=\vert S\vert$. The objective of this talk is to present time efficient and near space-optimal perfect hashing algorithms. We will present: (i) a family of internal memory based algorithms that assume uniform hashing to build PHFs (for $ m=1.23n$) and MPHFs (for $ m=n$) based on random graphs, and (ii) an external memory based algorithm that has experimentally proven practicality for sets in the order of billions of keys. Both internal and external algorithms have the following properties: (i) evaluation of a PHF or a MPHF requires constant time, (ii) the algorithms are simple to describe and implement, and generate the functions in linear time, (iii) the amount of space needed to represent a PHF is $ 1.95 n$ bits and a MPHF is $ 2.62 n$ bits, which is around a factor of 2 from the information theoretical minimum of approximately $ 1.17 n$ and $ 1.4427 n$ bits, respectively. To our knowledge, no previously known algorithm has these properties and any algorithm in the literature with the third property either requires exponential time for construction and evaluation, or uses near-optimal space only asymptotically, for extremely large $ n$. We demonstrate the scalability of the external memory based algorithm by constructing minimum perfect hash functions for a set of 1.024 billion URLs from the World Wide Web of average length 64 characters in approximately 62 minutes, using a commodity PC.

Nivio Ziviani

Nivio Ziviani has a Ph.D. in Computer Science from the University of Waterloo, Canada, 1982. He is a Professor of the Department of Computer Science of the Federal University of Minas Gerais (UFMG), Brazil, where he coordinates the Laboratory for Treating Information (LATIN). He is a Professor Emeritus of the Institute of Exact Sciences of UFMG. He is a co-founder of Miner Technology Group, sold to Folha de São Paulo / UOL group in 1999, and Akwan Information Technologies, sold to Google Inc. in 2005. He has co-authored of over 100 refereed papers and 2 books in the areas of algorithm design and information retrieval, the latter his primary area of research. He was General Co-Chair of the 28th ACM SIGIR Conference on Research and Development in Information Retrieval and co-founder of the International Conference on String Processing and Information Retrieval (SPIRE).