Succinct Data Structures for Retrieval and Approximate Membership
Succinct Data Structures for Retrieval and Approximate Membership
复制标题
用于检索和近似成员资格的简洁数据结构
DOI：
10.1007/978-3-540-70575-8_32
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Rasmus Pagh
中科院分区：
文献类型：
--
作者：
Martin Dietzfelbinger;Rasmus Pagh
检索问题是将数据与集合中的键相关联的问题。形式上，数据结构必须存储一个函数，该函数在给定的集合S U的元素上具有指定的值，|S| =n，但可以在S之外的元素上具有任何值。所有已知的方法（e. G.那些基于完美散列函数的算法），无论评估时间如何，都会引起超过最优值的Θ（n）比特的空间开销。我们证明了对于任意k，查询时间O（k）可以使用在1 + e-kof最优因子内的空间来实现，对于largen是渐近的。构造数据结构的时间是O（n），这是预期的。如果我们允许对数求值时间，则加法开销可以减少到O（loglogn）位whp。一个一般的减少转移检索的结果到类似的结果onapproximate会员资格，传统上使用布隆过滤器解决的问题。因此，我们也得到了任意接近这个问题的下界的空间界。我们的数据结构的评估过程非常简单。对于上述结果，我们假设可以自由访问完全随机的哈希函数。这个假设可以使用spaceo（n）来证明，以模拟RAM上的完全随机性。
Theretrieval problemis the problem of associating data with keys in a set. Formally, the data structure must store a functionthat has specified values on the elements of a given setS⊆U, |S| =n, but may have any value on elements outsideS. All known methods (e. g. those based on perfect hash functions), induce a space overhead ofΘ(n) bits over the optimum, regardless of the evaluation time. We show that for anyk, query timeO(k) can be achieved using space that is within a factor 1 +e−kof optimal, asymptotically for largen. The time to construct the data structure isO(n), expected. If we allow logarithmic evaluation time, the additive overhead can be reduced toO(loglogn) bits whp. A general reduction transfers the results on retrieval into analogous results onapproximate membership, a problem traditionally addressed using Bloom filters. Thus we obtain space bounds arbitrarily close to the lower bound for this problem as well. The evaluation procedures of our data structures are extremely simple. For the results stated above we assume free access to fully random hash functions. This assumption can be justified using spaceo(n) to simulate full randomness on a RAM.
登录
查看更多内容
在两次内存访问中进行查找的高效散列
DOI：
--
发表时间：
2004
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
R. Panigrahy
通讯作者：
R. Panigrahy
GF(q) 中常量权重向量的相关集
DOI：
--
发表时间：
1996
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
Neil J. Calkin
通讯作者：
Neil J. Calkin
DOI：
10.1145/380752.380842
发表时间：
2001
期刊：
J. ACM
影响因子：
--
作者：
Stephen Alstrup;G. Brodal;Theis Rauhe
通讯作者：
Theis Rauhe
DOI：
--
发表时间：
1995
期刊：
影响因子：
--
作者：
V. F. Kolchin;V. I. Khokhlov
通讯作者：
V. I. Khokhlov
最小完美哈希函数的设计策略
影响因子：
--
作者：
Martin Dietzfelbinger
通讯作者：
Martin Dietzfelbinger