Engineering Minimal $𝒌$-Perfect Hash Functions

When $m=\lceil n/k\rceil$, we obtain a minimal $k$-perfect hash function (M$k$PHF) [26]. When using the M$k$PHF to partition 1-PHFs [30, 31], it might be beneficial to look at a stricter definition where all output bins contain exactly $k$ keys, except possibly the last. The approaches presented in this paper fulfill the stricter definition. An alternative definition of non-minimal $k$PHFs could be that we could fill each output bin with either exactly $k$ keys or $0$ keys. For $k=1$, this results in an ordinary non-minimal PHF and achieves a significant reduction in space consumption. However, for $k>1$, the resulting space consumption is the same as the one of M$k$PHFs [33].

$k$-perfect hashing has a wide range of applications. In external memory hash tables, $k$PHFs can return the page on which a key is stored. External memory is usually accessed with page granularity anyway, so having to scan the page for the key only causes negligible overhead. Compared to a 1-PHF, however, this can significantly reduce the space needed. For internal memory hash tables it can be beneficial to store more than one key in each table cell [12]. Using an M$k$PHF, we can completely fill such a hash table. A $k$-perfect hash function can also be used to make the construction of 1-perfect hash functions more uniform by dividing the input to same-size partitions [30, 31].

In this paper, we present four new or significantly improved $k$-perfect hash function constructions. Threshold-based bumping was previously only briefly described as an ad-hoc solution to aid 1-perfect hashing [30, 31]. In Section 4, we extend it through optimal thresholds and Consensus-coded [31] thresholds. Perfect hashing through bucket placement [37, 20, 2] generalizes to $k$-perfect hashing in an obvious way. In Section 5, we introduce an optimal bucket assignment function. RecSplit [9] is a known 1-PHF, which we extend to a $k$-PHF in Section 6. Finally, we introduce a variant of the external memory hash table PaCHash [23] that can be used as an M$k$PHF in Section 7. To the best of our knowledge, we then give the first experimental evaluation of different $k$-perfect hash functions in Section 8.

The space lower bound for representing a minimal $k$-perfect hash function is rather easy to prove [32, 2, 23]. Let the $n$ input keys be a subset of a universe of size $u$. There are $\left(\genfrac{}{}{0pt}{}{u}{n}\right)$ possible input sets. Each behavior of an M$k$PHF can cover at most ${\left(\genfrac{}{}{0pt}{}{u/(n/k)}{k}\right)}^{n/k}$ input sets. Therefore, the number of bits we need is at least

In Table 1, we give a range of example values. The space lower bounds become more complex for non-minimal $k$-perfect hashing, and no tight bounds are known yet [2].

A retrieval data structure stores a static function $f:S\to {\{0,1\}}^r$ with $r$-bit output values. It can return arbitrary results for any key not in $S$. This makes it possible to represent it using just $rn$ bits. Bumped Ribbon Retrieval (BuRR) [7] is based on solving a system of linear equations and has a space consumption of $1.01rn$ bits in practice.

Let ${(a_i)}_{i\in [n]}$ be a monotonically increasing sequence of integers. To store this sequence with Elias-Fano coding [8, 11], we split each integer into two parts. We store the lower $L=\lceil {\log }_2(a_{n-1}/n)\rceil$ bits directly in a packed array. Then we store the remaining upper bits ${(h_i)}_{i\in [n]}$ as a bit vector where the bits at indices $h_i+i$ are 1, and all other bits are 0. On this bit vector, we have $h_i={\text{select}}_1(i)-i$. Together with a lookup in the packed array, we get constant access time. In total, storing the sequence needs $n\cdot (2+\lceil {\log }_2(a_{n-1}/n)\rceil )+o(n)$ bits of space [8, 11].

For a parameter $L$, Golomb-Rice coding [14, 38] divides an integer $x$ into the two parts $h=\lfloor x/2^L\rfloor$ and $l=x\text{ mod }{2}^L$. It encodes $l$ using $L$ bits in binary coding, and $h$ in unary coding. Golomb-Rice coding is optimal for geometrically distributed $x$ with $p=2^{-L}$. We can store a sequence of integers with constant time access by using a common array for the lower bits, concatenating the upper bits, and using a select data structure.

To determine $p_k(x)$, we model the following process where we insert $bk$ keys into $b$ bins of capacity $k$. We initialize a counter $c_i=0$ for each bin $i\in [b]$. The keys are handled sequentially as described in the following. For each key we uniformly sample bins. Sampling a bin $s\in [b]$ has two possible outcomes:

• $\mathrm{■}$

  (Success): We increment the counter $c_s$ by one and continue with the next key.

• $\mathrm{■}$

  $c_s\ge k$ (Failure): In this case, we also increment the counter $c_s$ by one. Note that this does not change anything in terms of success probabilities, since the bin is already full anyway. We continue with sampling a new bin for the same key.

The reason for incrementing the counter even if the bin is full is that the counter of each bin now follows a Poisson distribution (assuming that the number of bins $b$ is large). We show how $p_k(x)$ can be expressed as the solution of an integro-differential equation in the full version of this paper [18]. However, solving this equation is numerically unstable. In the following we give a numerically stable solution for $p_k(x)$. We repeatedly choose values $\mu$. We use each $\mu$ as the expected value of the Poisson distribution that describes the distribution of the counters. For each $\mu$ we calculate the probability $p$ that a key is inserted successfully, as well as the fraction of inserted keys $x$. Hence, for each $\mu$ we obtain $p$ and $x$ which we use to numerically determine $p_k(x)$. We choose the values $\mu$ such that the distance of consecutive $x$ values is sufficiently small. The success probability $p$ for a given $\mu$ is the probability that , which we calculate using the cumulative distribution function of the Poisson distribution. To determine the fraction of inserted keys $x$ for a given expected value $\mu$ we consider the counter of the bins as described in the model. For a bin where the counter is higher than $k$, we charge $k$ successfully inserted keys, because all other incrementations are from failures. We then divide by $k$, since we are interested in the relative number of inserted keys. Let $X$ follow a Poisson distribution with mean $\mu$ then $x=\frac{1}{k}(𝔼[X|X\le k]+k\mathbb{P}[X>k])=\frac{1}{k}𝔼[X|X\le k]+\mathbb{P}[X>k]$.

The final bucket assignment function can be obtained by numerically evaluating the integral of Equation 3 for ${\beta }_k(x)$. The constant $C_k$ can be ignored by normalizing the integral as a last step such that the boundary condition ${\beta }_k(1)=1$ is met. Refer to Figure 2(b) for an illustration of the bucket assignment functions with different values of $k$. Larger $k$ make the function more aggressive, further increasing the size of the first buckets. For example, for $k=100$, 82% of the keys are hashed to 1% of buckets. Our implementation tabulates the bucket assignment function for specific $k$ and uses linear interpolation to maintain a fast query time.

RecSplit [9] first hashes each key to a bucket of expected size $b$, where $b$ is a tuning parameter with default value $b=2000$ in the implementation. Within each bucket, RecSplit then uses brute-force to search for a hash function seed that divides the keys into two (or more) subsets. The number of these subsets (fanout) depends on the splitting strategy. This continues recursively until we are left with small input sets of $\le \mathrm{\ell }$ keys in the leaf nodes. These subsets are small enough that it is feasible to search for a perfect hash function using brute-force. RecSplit stores the hash function seeds determined at each node using Golomb-Rice coding (see Section 2) in DFS order. An Elias-Fano coded sequence (see Section 2) stores where the encoding of each bucket starts, as well as the total number of keys before it. A query traverses the splitting tree of the corresponding bucket, evaluating the hash function in each node. When descending into a subtree, it sums up the number of keys in sibling nodes left to it. Therefore, the final hash function value is given by the number of keys before the bucket, the number of keys to the left in the tree, and the final brute-force hash function value in the leaf. The RecSplit splitting strategy ensures that all subtrees except possibly the last are a complete tree where each leaf node receives exactly $\mathrm{\ell }$ keys. Therefore, only the very last leaf in any tree can have a size smaller than $\mathrm{\ell }$. We illustrate RecSplit in Figure 3. Through the use of the buckets, RecSplit achieves linear time construction and constant time queries.

Our $k$-perfect adaptation of RecSplit is (almost) straight-forward. We perform splittings until we are left with leaves of size $k$. These then do not need to store seeds. We now use the parameter $\mathrm{\ell }$ to select the fanout of the layer above. The main difficulty is that the last leaf in each bucket can have size . This would make the result a non-minimal $k$PHF. In Section 6.1, we explain how we can merge the leaves of adjacent buckets in order to get output bins of size $k$. As an alternative, in Section 6.2, we explain nested $k$-perfect hashing. This can avoid the problem by ensuring that each bucket’s size is a multiple of $k$.

To decide for one of the $d+1$ bins using only the index data structure, we use a $\lceil {\log }_2(d+1)\rceil$ bit retrieval data structure (see Section 2). The stored value tells us which of the bins to return. Since we rarely need more than one bit, we simply store the numbers bitwise in a single 1-bit retrieval data structure. Listing 3 gives the pseudocode of the query algorithm. PaCHash expects $1/a$ of the queries to load one external memory page too much [23]. In the context of $k$-perfect hashing, this means that for $1/a$ of the queries, the output bin is ambiguous. This means that the retrieval data structure essentially stores $n/a$ bits. By selecting $a=k$, we get a total space consumption of $n/k(3+\log (k))$, which already gets close to the lower bound for large $k$ (see Section 2). An advantage of the technique is that its construction through (integer) sorting and a single scan is very simple. Like the other approaches it takes linear time. Queries take expected constant time due to the distribution of values in the Elias-Fano data structure [23]. This adaptation is briefly mentioned in previous papers [27, 31] but without an implementation. The Consensus paper [31] gives a simple analysis for the resulting space consumption.

Compared to the ad-hoc implementation [31], our implementation of threshold-based bumping offers up to 3 times smaller space overhead due to the optimized thresholds. Only for $k=100$, the linearly spaced ad-hoc thresholds happen to be close to optimal, so we only achieve small space improvements. For growing $k$, threshold-based bumping gets closer to the space lower bound, while the space overhead of most other approaches increases. Figure 5(a) also shows that our implementation is up to 50% faster to construct than the next best technique. This is mainly because the ad-hoc implementation fully sorts the keys by their bin and fingerprint, while we only partition by the bin and then use quickselect [21] to find the $k$-th key. By packing using retrieval, we can achieve smaller space consumption. This has only a small influence on construction and query times. Finally, using Consensus-coded thresholds, we achieve smaller space consumption but slower construction and queries.

For the hash and displace technique, Rice coding (see Section 2) achieves lower space consumption than compact coding at the same construction time. This comes at the cost of slower queries, as can be seen in Figure 5(b), due to the select queries. Compared to CHD [2], an implementation from the literature, our construction is much faster. Even though we use CHD with a load factor of just 97%, our construction gets close to its space consumption. The CHD implementation from the literature crashes for $k=1000$, while our implementation supports large $k$ as well. Our measurements show that the hash and displace technique with compact coding is fast to query, especially for smaller $k$. This is in contrast to the implementation from the literature, which has much slower queries. In general, the hash and displace technique seems not competitive for $k$-perfect hashing, especially for large $k$.

Our $k$-perfect adaptation of RecSplit achieves the smallest space consumption. With just 10% overhead over the lower bound, it has a large margin to the next smallest competitor. This is not surprising, since the RecSplit paper [9] shows that the recursive splitting idea converges towards the space lower bound. However, its construction is significantly slower than the other approaches in Figure 5(a). Because splittings become even more expensive for large $k$, we do not include the configuration with 10% space overhead for $k=1000$. The queries are slow compared to other approaches.

Our $k$-perfect adaptation of PaCHash is very simple to describe and fast to construct through sorting followed by a linear scan. However, its queries are slow due to the predecessor queries in the Elias-Fano coded sequence of bucket indexes.

This paper revives the research area of $k$-perfect hashing. In the future, we expect a wide range of new techniques, like there is in 1-perfect hashing. The approaches presented in this paper give a starting point outlining the trade-off. Especially our improvements to threshold-based bumping can now be used to improve the space efficiency of Consensus-RecSplit [31]. An open theoretical problem is the space lower bound for non-minimal $k$-perfect hashing.