File RecSplit.h

↰ Parent directory (ADS/dictionary)

The minimal perfect hash function of Namespace ADS by recursive splitting, the RecSplit of Esposito, Mueller Graf and Vigna, beyond the book [see File MinimalPerfectHash.h for the one by pilots, faster but about 3 bits per key]: a function that maps the n distinct keys of a static set S onto :math:` { 0 , ldots , n - 1 } ` with no collision in about 1.8 bits per key for the leaves of 8 keys and the buckets of 100, against the lower bound of :math:` log_2 e approx 1.4427 ` bits per key of any minimal perfect hash function.

Definition (ADS/dictionary/RecSplit.h)

Detailed Description

A key goes to the bucket :math:` lfloor h_1 lceil n / b rceil / 2^{64} rfloor ` of :math:` lceil n / b rceil ` buckets, b keys each on average, by its first hash :math:` h_1 ; the m keys of a bucket are then split recursively by their second hash :math: h_2 , so that each leaf of the splitting tree holds at most :math: ell ` keys (the template parameter L). A node of m keys with the seed x sends a key to the place :math:` rho_x = lfloor g_{x , d}( h_2 ) , m / 2^{64} rfloor in [ 0 , m ) , where :math: g_{x , d} ` is a folded product salted by x and by the depth d of the node, and its children by the place:

  • a leaf ( :math:` m le ell ) needs a bijection, the seed x for which the m places are distinct, with probability :math: m! / m^m , so that its expected trials are :math: m^m / m! approx e^m / sqrt{ 2 pi m } `;

  • a node of :math:` ell < m le s ell ` keys, :math:` s = max{ 2 , lceil 0.35 ell + 0.5 rceil } ` (the lower aggregation), goes into parts of :math:` ell ` keys, the part :math:` lfloor rho_x / ell rfloor `, the last one with the rest;

  • a node of :math:` s ell < m le t s ell ` keys, :math:` t = lceil 0.21 ell + 0.9 rceil ` for :math:` ell ge 7 ` and 2 below (the upper aggregation), into parts of :math:` s ell ` keys in the same way;

  • a larger node into two parts, of :math:` u = lceil lfloor m / 2 rfloor / ( t s ell ) rceil , t s ell ` and :math:` m - u ` keys, by :math:` rho_x < u `.

The seed of a node is the first x that gives each part its size, with probability :math:`[

p = frac{ m! }{ k_0! cdots k_{s-1}! } prod_{i} Bigl( frac{ k_i }{ m } Bigr)^{ k_i }

` for the parts of :math:` k_0 , ldots , k_{s-1} ` keys, so that the seed is geometric of parameter p and the product of the probabilities of all the nodes of a tree of m keys is :math:` m! / m^m ` whatever the shape (the invariance of RecSplit). The seeds are written in preorder by a code of Golomb and Rice, whose parameter for a geometric source of parameter p is the optimal one of Kiely, :math:`[

r( p ) = maxBigl{ 0 , Bigllceil log_2 frac{ -log_2 varphi }{ log_2 ( 1 - p ) } Bigrrceil Bigr} , qquad varphi = frac{ 1 + sqrt{ 5 } }{ 2 } ,

` a function of m alone, so that the code of a seed takes :math:` c + log_2 ( 1 / p ) ` bits in expectation with :math:` 1.56 le c < 2.56 , and a tree of m keys with t nodes :math: c t + m log_2 e + O( log m ) ` bits. The r( p ) low bits of all the seeds of a bucket come first, then all their unary parts; a table of the sizes :math:` m < 4096 , computed once for each :math: ell , gives r, the low bits of a subtree and its number of nodes, so that a subtree is skipped by moving a pointer on the low bits and by a select on the unary parts. The numbers of keys before each bucket and the place of its code are two Elias-Fano sequences, the second one less :math: beta ` times the first, for the :math:` beta ` bits per key of the codes, and both less i times their least gap, which leaves to their low bits only the deviations from the average; each keeps the place of every 64th 1 of its high bits, 64 bits per 64 buckets, so that a query costs two selects of one or two words each instead of the searches of a general select, the numbers of keys before the bucket and before the next one coming from the same select; the select in a word, there and in the unary parts, is one PDEP and one count of the trailing zeros where the machine has BMI2.

The search of a leaf uses the rotation fitting of Bez, Kurpicz, Lehmann and Sanders: the keys of the leaf go to two sets A and B by the highest bit of :math:` h_2 ; for each x, the places of A and of B are two masks of m bits (x is discarded if a set has two keys in one place), and the leaf takes the seed :math: x m + r ` for the first rotation r of the mask of B that fills the holes of the mask of A. A key of B goes to the place :math:` ( rho_x + r ) bmod m ; each x tries m rotations, so that the leaf evaluates about m times fewer hashes for the same expected seed. The leaves of :math: ell le 24 ` keys fit in a word, and the search grows as :math:` e^ell : 1 <= L <= 24 (a build at :math: ell = 16 ` is already slow).

An evaluation computes the two hashes and the bucket, reads the three values of the Elias-Fano sequences (three select) and descends the :math:` O( log ( b / ell ) ) ` levels of the tree, each one a read of the low bits, a scan of the unary part and, to skip the earlier siblings, a select in a word or a few; the build takes expected :math:` O( n , e^ell / ( ell sqrt{ ell } ) ) ` time. For a key out of S the result is some place below n.

The keys are hashed by h( k ), taken as it is if H declares is_avalanching [see File FastHash.h] and mixed by hashWord() otherwise; the two hashes of 64 bits are two folded products of that hash XOR the seed, 128 bits per key. Two keys of a bucket with the same :math:` h_2 `, or a bucket of 4096 keys or more, make the build draw a new seed; two keys with the same hash of 64 bits cannot be separated.

Consensus-RecSplit of Lehmann, Sanders, Walzer and Ziegler is the space frontier of this family: it searches the seeds of consecutive nodes together, each one a continuation of the bits of the previous ones, and takes :math:` ( 1 + varepsilon ) , n log_2 e ` bits in :math:` O( n / varepsilon ) ` expected time.

The contracts [see File Contract.h]: the keys distinct (an audit), fewer than :math:` 2^{32} `, 1 <= b <= 2000; after the build the keys are mapped onto { 0 , … , n - 1 }, an audit. A build that draws 100 seeds with no success throws std::runtime_error. The operations are defined in RecSplit.tpp.

  1. Esposito, T. Mueller Graf, S. Vigna, RecSplit: minimal perfect hashing via recursive splitting, Proceedings of the 22nd Workshop on Algorithm Engineering and Experiments (ALENEX 2020), 175-185, 2020, doi:10.1137/1.9781611976007.14

    1. Golomb, Run-length encodings, IEEE Transactions on Information Theory 12(3), 399-401, 1966, doi:10.1109/TIT.1966.1053907

  1. Kiely, Selecting the Golomb parameter in Rice coding, IPN Progress Report 42-159, Jet Propulsion Laboratory, 1-18, 2004, https://ipnpr.jpl.nasa.gov/progress_report/42-159/159E.pdf

  1. Elias, Efficient storage and retrieval by content and address of static files, Journal of the ACM 21(2), 246-260, 1974, doi:10.1145/321812.321820

  1. Bez, F. Kurpicz, H.-P. Lehmann, P. Sanders, High performance construction of RecSplit based minimal perfect hash functions, Proceedings of the 31st European Symposium on Algorithms (ESA 2023), LIPIcs 274, 19:1-19:16, 2023, doi:10.4230/LIPIcs.ESA.2023.19

H.-P. Lehmann, P. Sanders, S. Walzer, J. Ziegler, Combined search and encoding for seeds, with an application to minimal perfect hashing, Proceedings of the 33rd European Symposium on Algorithms (ESA 2025), LIPIcs 351, 109:1-109:18, 2025, doi:10.4230/LIPIcs.ESA.2025.109

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes

Functions