Near-Optimal Space Perfect Hashing Algorithms

Present a perfect hashing algorithm that uses the idea of partitioning the input key set into small buckets: Key set fits in the internal memory Internal Random Access Memory algorithm (RAM) LATIN- LAboratory for Treating INformation (www.dcc.ufmg.br/latin) 2 Key set larger than the internal memory External Memory (cache-aware) algorithm (EM) Objective of the Presentation Present a perfect hashing algorithm that uses the idea of partitioning the input key set into small buckets: Key set fits in the internal memory Internal Random Access Memory algorithm (RAM) LATIN- LAboratory for Treating INformation (www.dcc.ufmg.br/latin) 3 Key set larger than the internal memory External Memory (cache-aware) algorithm (EM) Theoretically well-founded, time efficient, higly scalable and near space-optimal Perfect Hash Function Static key set S of size