One-Probe Search
One-Probe Search
复制标题
单探针搜索
DOI：
10.1007/3-540-45465-9_38
复制
发表时间：
2002
影响因子：
--
通讯作者：
R. Pagh
中科院分区：
文献类型：
--
作者：
Anna Pagh;R. Pagh
我们考虑通过探测单个内存单词来执行查找的字典，仅知道数据结构的大小。我们描述了一个随机词典，其中查找以概率1-？返回正确的答案，否则返回“不知道”。查找过程使用扩展器图来选择要探测的内存位置。显示最新的显式扩展器结构的产生的空间用法远小于确定性查找过程所需的空间。我们的数据结构支持有效的确定性更新，并在字典运行时间内显示出新的固定型保证。
We consider dictionaries that perform lookups by probing a single word of memory, knowing only the size of the data structure. We describe a randomized dictionary where a lookup returns the correct answer with probability 1 - ?, and otherwise returns "don't know". The lookup procedure uses an expander graph to select the memory location to probe. Recent explicit expander constructions are shown to yield space usage far smaller than what would be required using a deterministic lookup procedure. Our data structure supports efficient deterministic updates, exhibiting newprobabilistic guarantees on dictionary running time.