XOR-Satisfiability Set Membership Filters
XOR-Satisfiability Set Membership Filters
复制标题
XOR-可满足性集成员过滤器
DOI：
10.1007/978-3-319-94144-8_24
复制
发表时间：
2018
期刊：
影响因子：
3.7
通讯作者：
Michael J. Smith
中科院分区：
文献类型：
--
作者：
S. Weaver;Hannah J. Roberts;Michael J. Smith
设置会员资格过滤器被用作主要测试，用于大型集合是否包含给定的元素。最常见的过滤器是Bloom过滤器[6]。与本文最相关的是最近引入的满意度（SAT）过滤器[31]。本文提出了基于随机K-Xorsat的SAT滤波器的变体XOR-可满足过滤器。实验结果表明，该新过滤器的效率可能超过\（99 \％\）（即实现信息理论限制），同时还具有与标准布鲁姆过滤器相当的查询速度数据集。
Set membership filters are used as a primary test for whether large sets contain given elements. The most common such filter is the Bloom filter [6]. Most pertinent to this article is the recently introduced Satisfiability (SAT) filter [31]. This article proposes the XOR-Satisfiability filter, a variant of the SAT filter based on random k-XORSAT. Experimental results show that this new filter can be more than \(99\%\) efficient (i.e., achieve the information-theoretic limit) while also having a query speed comparable to the standard Bloom filter, making it practical for use with very large data sets.
用于检索和近似成员资格的简洁数据结构
DOI：
10.1007/978-3-540-70575-8_32
发表时间：
2008
期刊：
影响因子：
--
作者：
Martin Dietzfelbinger;Rasmus Pagh
通讯作者：
Rasmus Pagh