论文标题
具有恒定时间操作的动态空间有效过滤器
A Dynamic Space-Efficient Filter with Constant Time Operations
论文作者
论文摘要
动态词典是一种数据结构，该数据结构最多可以从给定的宇宙中维护最多$ n $的基数，并支持插入，删除和会员查询。过滤器近似于会员查询，其单方面误差最多为$ε$。目的是获得空间效率的动态过滤器（空间为$ 1+o（1）$乘以信息理论下限），并以较高的概率在恒定时间内支持所有操作。设计过滤器的一种方法是减少检索问题。当宇宙的大小在$ n $中是多项式时，只要误差参数$ε$满足$ \ log（1/ε）=ω（\ log \ log \ log \ log n）$，此方法就会产生一个空间有效的动态过滤器。 对于$ \ log（1/ε）= o（\ log \ log n）$的情况，我们介绍了在最坏情况下（WHP）中使用恒定时间操作的第一个空间效率动态过滤器。相比之下，PAGH，PAGH，RAO（SODA 2005）的空间有效滤波器支持摊销预期恒定时间的插入和缺失。我们的方法采用了Carter等人的经典减少。 （STOC 1978）关于支持随机多组的新型字典结构。
A dynamic dictionary is a data structure that maintains sets of cardinality at most $n$ from a given universe and supports insertions, deletions, and membership queries. A filter approximates membership queries with a one-sided error that occurs with probability at most $ε$. The goal is to obtain dynamic filters that are space-efficient (the space is $1+o(1)$ times the information-theoretic lower bound) and support all operations in constant time with high probability. One approach to designing filters is to reduce to the retrieval problem. When the size of the universe is polynomial in $n$, this approach yields a space-efficient dynamic filter as long as the error parameter $ε$ satisfies $\log(1/ε) = ω(\log\log n)$. For the case that $\log(1/ε) = O(\log\log n)$, we present the first space-efficient dynamic filter with constant time operations in the worst case (whp). In contrast, the space-efficient dynamic filter of Pagh, Pagh, Rao (SODA 2005) supports insertions and deletions in amortized expected constant time. Our approach employs the classic reduction of Carter et al. (STOC 1978) on a new type of dictionary construction that supports random multisets.
