File FingerprintPerfectHash.h

↰ Parent directory (ADS/dictionary)

The minimal perfect hash function by fingerprinting, beyond the book: the method of Müller, Sanders, Schulze and Zhou, engineered as BBHash by Limasset et al.

Definition (ADS/dictionary/FingerprintPerfectHash.h)

Detailed Description

and as FMPH by Beling, a function that maps the n distinct keys of a static set S onto :math:` { 0 , ldots , n - 1 } ` in about :math:` gamma e^{1 / gamma} ` bits per key, built in a few passes over the keys [see File MinimalPerfectHash.h for the function by pilots, fewer bits and faster queries but a slower build, and File RecSplit.h for the fewest bits].

The keys go through levels :math:` 0 , 1 , ldots : the level i is a vector of :math: m_i = lceil gamma n_i rceil ` bits for the :math:` n_i ` keys that reach it ( :math:` n_0 = n , the sizes rounded up to blocks of 512 bits), each key hashed to a place :math: h_i( k ) ` of it; the bit of a place is 1 if exactly one key falls there, and the keys that share their place with others go to the next level. A key k is then mapped to the number of 1s before its bit in the concatenation of the levels, the rank of the first level i whose bit :math:` h_i( k ) ` is 1, which is a bijection of S onto :math:` { 0 , ldots , n - 1 } ` since every key has one bit of its own and every 1 belongs to one key. A key is alone in its place with probability :math:` ( 1 - 1 / m_i )^{n_i - 1} approx e^{-1 / gamma} `, so that :math:`[

E[ n_{i+1} ] approx n_i ( 1 - e^{-1/gamma} ) , qquad sum_i m_i approx gamma n sum_i ( 1 - e^{-1/gamma} )^i = gamma e^{1 / gamma} n ,

` 3.30 bits per key for :math:` gamma = 2 , 2.72 (e) for :math: gamma = 1 , the least, and the expected number of levels a key of S goes through is :math: e^{1 / gamma} , 1.65 for :math: gamma = 2 : a smaller :math: gamma ` saves bits and costs levels, in the build and in the queries. The number of levels is :math:` O( log n ) ` with high probability.

The build hashes each key once, to a word x of 64 bits, and each level hashes x again by a folded product with a constant of its own, :math:` h_i( k ) = lfloor m_i , g( x oplus s_i , c_i ) / 2^{64} rfloor ; a level is two passes over its keys: the first sets in a vector A the bit of each place and in a vector C the bits of the places met twice, :math: A leftarrow A wedge neg C ` a word at a time, and the second keeps the keys whose place is in C. The vectors of a level take :math:` 2 gamma n_i ` bits, about 0.5 MB for :math:` 10^6 ` keys, and stay in the cache of level 2, so that a key costs a few nanoseconds per level. A query computes :math:` h_0( k ) `, tests its bit and, if it is 1, gives its rank: the number of 1s before each block of 512 bits is kept in 32 bits (1 / 16 of the bits more), so that a rank costs at most 8 counts of the bits of a word. For a key out of S the result is some value 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 (an integer key under FastHash is taken as it is, the levels mixing it). Two keys with the same hash of 64 bits meet at every level and cannot be separated: the build throws std::runtime_error.

The contracts [see File Contract.h]: the keys distinct (an audit), fewer than :math:` 2^{32} , :math: gamma ge 1 `; after the build the keys are mapped onto { 0 , … , n - 1 }, an audit. The operations are defined in FingerprintPerfectHash.tpp.

  1. Müller, P. Sanders, R. Schulze, W. Zhou, Retrieval and perfect hashing using fingerprinting, Proceedings of SEA 2014, Lecture Notes in Computer Science 8504, 138-149, 2014, doi:10.1007/978-3-319-07959-2_12

  1. Limasset, G. Rizk, R. Chikhi, P. Peterlongo, Fast and scalable minimal perfect hashing for massive key sets, Proceedings of SEA 2017, LIPIcs 75, 25:1-25:16, 2017, doi:10.4230/LIPIcs.SEA.2017.25

  1. Beling, Fingerprinting-based minimal perfect hashing revisited, ACM Journal of Experimental Algorithmics 28, 1-16, 2023, doi:10.1145/3596453

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes