Tight Bounds For Monotone Minimal Perfect Hashing

Assadi Sepehr, Farach-colton Martin, Kuszmaul William. Arxiv 2022

[Paper]    
ARXIV Graph Independent

The monotone minimal perfect hash function (MMPHF) problem is the following indexing problem. Given a set $S=\{s_1,\dots ,s_n\}$ of $n$ distinct keys from a universe $U$ of size $u$, create a data structure $DS$ that answers the following query: [ RankOp(q) = \text{rank of } q \text{ in } S \text{ for all } q\in S ~\text{ and arbitrary answer otherwise.} ] Solutions to the MMPHF problem are in widespread use in both theory and practice. The best upper bound known for the problem encodes $DS$ in $O(nlogloglogu)$ bits and performs queries in $O(logu)$ time. It has been an open problem to either improve the space upper bound or to show that this somewhat odd looking bound is tight. In this paper, we show the latter: specifically that any data structure (deterministic or randomized) for monotone minimal perfect hashing of any collection of $n$ elements from a universe of size $u$ requires $\Omega (n\cdot logloglogu)$ expected bits to answer every query correctly. We achieve our lower bound by defining a graph $\mathbf{G}$ where the nodes are the possible $(\genfrac{}{}{0ex}{}{u}{n})$ inputs and where two nodes are adjacent if they cannot share the same $DS$. The size of $DS$ is then lower bounded by the log of the chromatic number of $\mathbf{G}$. Finally, we show that the fractional chromatic number (and hence the chromatic number) of $\mathbf{G}$ is lower bounded by $2^{\Omega (nlogloglogu)}$.

Similar Work

• Recsplit Minimal Perfect Hashing Via Recursive Splitting
• Learned Monotone Minimal Perfect Hashing
• Approximate Nearest Neighbors In Limited Space
• De Dictionariis Dynamicis Pauco Spatio Utentibus