Many applications of approximate membership query data structures, or filters, require only an incremental filter that supports insertions but not deletions. However, the design space of incremental filters is missing a "sweet spot" filter that combines space efficiency, fast queries, and fast insertions. Incremental filters, such as the Bloom and blocked Bloom filter, are not space efficient. Dynamic filters (i.e., supporting deletions), such as the cuckoo or vector quotient filter, are space efficient but do not exhibit consistently fast insertions and queries. In this paper, we propose the prefix filter, an incremental filter that addresses the above challenge: (1) its space (in bits) is similar to state-of-the-art dynamic filters; (2) query throughput is high and is comparable to that of the cuckoo filter; and (3) insert throughput is high with overall build times faster than those of the vector quotient filter and cuckoo filter by $1.39\times$-$1.46\times$ and $3.2\times$-$3.5\times$, respectively. We present a rigorous analysis of the prefix filter that holds also for practical set sizes (i.e., $n=2^{25}$). The analysis deals with the probability of failure, false positive rate, and probability that an operation requires accessing more than a single cache line.


翻译:近似会籍查询数据结构或过滤器的许多应用只需要一个支持插入而不是删除的递增过滤器。 但是, 递增过滤器的设计空间缺少一个“ 甜点” 过滤器, 将空间效率、 快速查询和快速插入结合起来。 递增过滤器, 如Bloom 和屏蔽 Bloom 过滤器等递增过滤器, 没有空间效率。 动态过滤器( 支持删除), 如 cuckoo 或矢量过滤器等, 空间效率很高, 但没有一贯快速插入和查询。 在本文中, 我们提议使用前缀过滤器, 是一个应对上述挑战的递增过滤器:(1) 其空间( 位数) 类似于最先进的动态过滤器; (2) 查询管道高, 与 cuckoo 过滤器相似; (3) 插入通量比矢量过滤器和库过滤器总体建设速度快1.39\ time, $1. 46\time, 和 3.2\time $ 递增 33.5\ time 美元。 我们使用一个精确度的精确度分析, 和精确度的精确度, 。

0
下载
关闭预览

相关内容

FAST:Conference on File and Storage Technologies。 Explanation:文件和存储技术会议。 Publisher:USENIX。 SIT:http://dblp.uni-trier.de/db/conf/fast/
【硬核书】树与网络上的概率,716页pdf
专知会员服务
72+阅读 · 2021年12月8日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
17+阅读 · 2020年9月6日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
Call for Nominations: 2022 Multimedia Prize Paper Award
CCF多媒体专委会
0+阅读 · 2022年2月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium8
中国图象图形学学会CSIG
0+阅读 · 2021年11月16日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2022年12月12日
Arxiv
0+阅读 · 2022年12月11日
Arxiv
0+阅读 · 2022年12月9日
Arxiv
0+阅读 · 2022年12月8日
VIP会员
相关VIP内容
【硬核书】树与网络上的概率,716页pdf
专知会员服务
72+阅读 · 2021年12月8日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
17+阅读 · 2020年9月6日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
Call for Nominations: 2022 Multimedia Prize Paper Award
CCF多媒体专委会
0+阅读 · 2022年2月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium8
中国图象图形学学会CSIG
0+阅读 · 2021年11月16日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员