论文标题
单调最小的完美哈希的紧密界限
Tight Bounds for Monotone Minimal Perfect Hashing
论文作者
论文摘要
单调最小的完美哈希功能（MMPHF）问题是以下索引问题。给定一个$ s = \ {s_1，\ ldots，s_n \} $ $ n $ of $ n $ jubs of Universe $ u $ size $ u $ u $的键，创建一个数据结构$ ds $，回答以下查询： \ [rankop（q）= \ text {等级} q \ text {in} s \ text {for as all} q \ in s 〜\ text {和任意答案否则。} \] MMPHF问题的解决方案在理论和实践中都广泛使用。 以问题而闻名的最佳上限是编码$ o（n \ log \ log \ log \ log u）$ bits中的$ ds $，并在$ o（\ log u）$ time中执行查询。改善空间上限或表明这种看起来有些奇怪的界限是一个开放的问题。 在本文中，我们展示了后者：特别是单调的任何数据结构（确定性或随机化）最小的完美哈希是$ u $ $ u $的$ n $元素的任何集合的$ n $元素，需要$ω（n \ cdot \ cdot \ log \ log \ log \ log \ log {u} u {u}）$预期的bit可以正确答案。 我们通过定义图$ \ mathbf {g} $来实现下限，其中节点是可能的$ {u \ select n} $输入，如果两个节点不能共享相同的$ ds $，则两个节点相邻。然后，$ ds $的大小由$ \ mathbf {g} $的色数的日志降低。最后，我们表明$ \ mathbf {g} $的分数色度数（以及色数）由$ 2^{ω（n \ log \ log \ log \ log \ log u）} $降低。
The monotone minimal perfect hash function (MMPHF) problem is the following indexing problem. Given a set $S= \{s_1,\ldots,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(n\log\log\log u)$ bits and performs queries in $O(\log u)$ 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 $Ω(n \cdot \log\log\log{u})$ expected bits to answer every query correctly. We achieve our lower bound by defining a graph $\mathbf{G}$ where the nodes are the possible ${u \choose 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^{Ω(n \log\log\log u)}$.
