FCH Algorithm


The Algorithm

The algorithm is presented in [1].


Memory Consumption

Now we detail the memory consumption to generate and to store minimal perfect hash functions using the FCH algorithm. The structures responsible for memory consumption are in the following:

Thus, the total memory consumption of FCH algorithm for generating a minimal perfect hash function (MPHF) is: O(n) + 9n + 8cn/(log(n) + 1) bytes. The value of parameter c must be greater than or equal to 2.6.

Now we present the memory consumption to store the resulting function. We only need to store the g function and a constant number of bytes for the seed of the hash functions used in the resulting MPHF. Thus, we need cn/(log(n) + 1) + O(1) bytes.


Papers

  1. E.A. Fox, Q.F. Chen, and L.S. Heath. A faster algorithm for constructing minimal perfect hash functions. In Proc. 15th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 266-273, 1992.

Home CHD BDZ BMZ CHM BRZ FCH

Enjoy!

Davi de Castro Reis

Djamel Belazzougui

Fabiano Cupertino Botelho

Nivio Ziviani

VigLink badge