Dynamic Dictionaries for Multisets and Counting Filters with Constant Time Operations
Dynamic Dictionaries for Multisets and Counting Filters with Constant Time Operations
复制标题
用于多重集和具有恒定时间运算的计数过滤器的动态字典
DOI：
10.1007/978-3-030-83508-8_11
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Even, Guy
中科院分区：
文献类型：
--
作者：
Bercea, Ioana O.;Even, Guy
我们解决了Arbitman、Naor和Segev [FOCS 2010]提出的在以下设置中设计多重集动态字典的开放问题：（1）字典支持多重性查询并允许对多重集进行插入和删除。(2)字典被设计为支持基数的多集合（即，包括多重性）。(3)字典所需的空间是位，其中表示元素的宇宙的基数。这个空间是信息论下界的两倍，静态字典在多集的基数。(4)在字RAM模型中，在最坏的情况下，所有操作都在恒定的时间内完成，概率很高。我们构造的直接结果是第一个动态计数滤波器（即，一种动态数据结构，支持近似多重性查询，具有单侧错误），以高概率支持恒定时间内的操作，并需要的空间是过滤器的信息理论下限的倍加上O（n）位。我们的解决方案的主要技术组成部分是基于有效地存储可变长度有界二进制计数器和它的分析，通过加权球入箱实验，其中球的重量是对数的多重性。
We resolve the open problem posed by Arbitman, Naor, and Segev [FOCS 2010] of designing a dynamic dictionary for multisets in the following setting: (1) The dictionary supports multiplicity queries and allows insertions and deletions to the multiset. (2) The dictionary is designed to support multisets of cardinality at mostn(i.e., including multiplicities). (3) The space required for the dictionary isbits, whereudenotes the cardinality of the universe of the elements. This space istimes the information-theoretic lower bound for static dictionaries over multisets of cardinalitynif. (4) All operations are completed in constant time in the worst case with high probability in the word RAM model. A direct consequence of our construction is the first dynamic counting filter (i.e., a dynamic data structure that supports approximate multiplicity queries with a one-sided error) that, with high probability, supports operations in constant time and requires space that istimes the information-theoretic lower bound for filters plusO(n) bits. The main technical component of our solution is based on efficiently storing variable-length bounded binary counters and its analysis via weighted balls-into-bins experiments in which the weight of a ball is logarithmic in its multiplicity.
登录
查看更多内容
在两次内存访问中进行查找的高效散列
DOI：
--
发表时间：
2004
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
R. Panigrahy
通讯作者：
R. Panigrahy
搜索和排序
DOI：
10.1007/978-1-4842-3988-9_10
发表时间：
2021
期刊：
Data Structure and Algorithms Using C++
影响因子：
--
作者：
Sammie Bae
通讯作者：
Sammie Bae
DOI：
10.1007/978-3-642-02927-1_30
发表时间：
2009
期刊：
影响因子：
--
作者：
Martin Dietzfelbinger;Michael Rink
通讯作者：
Michael Rink
带重新分配的双向链接
DOI：
10.1137/s0097539704443240
发表时间：
2005
期刊：
SIAM J. Comput.
影响因子：
--
作者：
Ketan Dalal;L. Devroye;Ebrahim Malalla;E. McLeish
通讯作者：
E. McLeish
影响因子：
3.7
作者：
Fan, L;Cao, P;Broder, AZ
通讯作者：
Broder, AZ