BDZ Algorithm

Introduction

Coming soon...

The Algorithm

Coming soon...

Mapping Step

Coming soon...

Assigning Step

Coming soon...

Ranking Step

Coming soon...

Memory Consumption

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

• 3-graph:
  1. first: is a vector that stores cn integer numbers, each one representing the first edge (index in the vector edges) in the list of incident edges of each vertex. The integer numbers are 4 bytes long. Therefore, the vector first is stored in 4cn bytes.

  2. edges: is a vector to represent the edges of the graph. As each edge is compounded by three vertices, each entry stores three integer numbers of 4 bytes that represent the vertices. As there are n edges, the vector edges is stored in 12n bytes.

  3. next: given a vertex , we can discover the edges that contain following its list of incident edges, which starts on first[] and the next edges are given by next[...first[]...]. Therefore, the vectors first and next represent the linked lists of edges of each vertex. As there are three vertices for each edge, when an edge is iserted in the 3-graph, it must be inserted in the three linked lists of the vertices in its composition. Therefore, there are 3n entries of integer numbers in the vector next, so it is stored in 4*3n = 12n bytes.

  4. Vertices degree (vert_degree vector): is a vector of cn bytes that represents the degree of each vertex. We can use just one byte for each vertex because the 3-graph is sparse, once it has more vertices than edges. Therefore, the vertices degree is represented in cn bytes.

• Acyclicity test:
  1. List of deleted edges obtained when we test whether the 3-graph is a forest (queue vector): is a vector of n integer numbers containing indexes of vector edges. Therefore, it requires 4n bytes in internal memory.

  2. Marked edges in the acyclicity test (marked_edges vector): is a bit vector of n bits to indicate the edges that have already been deleted during the acyclicity test. Therefore, it requires n/8 bytes in internal memory.

• MPHF description
  1. function g: is represented by a vector of 2cn bits. Therefore, it is stored in 0.25cn bytes
  2. ranktable: is a lookup table used to store some precomputed ranking information. It has (cn)/(2^b) entries of 4-byte integer numbers. Therefore it is stored in (4cn)/(2^b) bytes. The larger is b, the more compact is the resulting MPHFs and the slower are the functions. So b imposes a trade-of between space and time.
  3. Total: 0.25cn + (4cn)/(2^b) bytes

Thus, the total memory consumption of BDZ algorithm for generating a minimal perfect hash function (MPHF) is: (28.125 + 5c)n + 0.25cn + (4cn)/(2^b) + O(1) bytes. As the value of constant c may be larger than or equal to 1.23 we have:

Now we present the memory consumption to store the resulting function. So we have:

Experimental Results

Experimental results to compare the BDZ algorithm with the other ones in the CMPH library are presented in Botelho, Pagh and Ziviani [1,2].

Papers

1. F. C. Botelho, R. Pagh, N. Ziviani. Simple and space-efficient minimal perfect hash functions. 10th International Workshop on Algorithms and Data Structures (WADs'07), Springer-Verlag Lecture Notes in Computer Science, vol. 4619, Halifax, Canada, August 2007, 139-150.

2. F. C. Botelho. Near Space-Optimal Perfect Hashing Algorithms. Thesis Proposal, Department of Computer Science, Federal University of Minas Gerais, July 2007.

Enjoy!

Davi de Castro Reis

Djamel Belazzougui

Fabiano Cupertino Botelho