On the cell probe complexity of membership and perfect hashing
On the cell probe complexity of membership and perfect hashing
复制标题
关于单元探测成员资格的复杂性和完美散列
DOI：
10.1145/380752.380836
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
R. Pagh
中科院分区：
文献类型：
--
作者：
R. Pagh
研究了姚单元探测模型中两个基本的静态数据结构问题：隶属度和完美哈希。给出了隶属度问题的第一个空间和位探针最优最坏情况上界。我们还提出了一种新的高效的隶属度方案，该方案的查询算法只做一个自适应选择，并且总共探测三个单词。下界表明两个单词探查通常是不够的。对于最小完美哈希，我们给出了一个紧位探测下界，并给出了一个简单的方案来实现这个性能，只做一个自适应选择。线性范围完美哈希可以用相同数量的位探针实现，其中只有一个是自适应的。相反，我们建立了对于充分稀疏集，非自适应完美哈希需要指数级多的位探针。这是第一次将适应性和非适应性区分开来。
We study two fundamental static data structure problems, membership and perfect hashing, in Yao's cell probe model. The first space and bit probe optimal worst case upper bound is given for the membership problem. We also give a new efficient membership scheme where the query algorithm makes just one adaptive choice, and probes a total of three words. A lower bound shows that two word probes generally do not suffice. For minimal perfect hashing we show a tight bit probe lower bound, and give a simple scheme achieving this performance, making just one adaptive choice. Linear range perfect hashing is shown to be implementable with the same number of bit probes, of which just one is adaptive. In contrast, we establish that for sufficiently sparse sets, non-adaptive perfect hashing needs exponentially more bit probes. This is the first such separation of adaptivity and non-adaptivity.