In the last decade, significant efforts have been made to reduce the false positive rate of approximate membership checking structures. This has led to the development of new structures such as cuckoo filters and xor filters. Adaptive filters that can react to false positives as they occur to avoid them for future queries to the same elements have also been recently developed. In this paper, we propose a new type of static filters that completely avoid false positives for a given set of negative elements and show how they can be efficiently implemented using xor probing filters. Several constructions of these filters with a false positive free set are proposed that minimize the memory and speed overheads introduced by avoiding false positives. The proposed filters have been extensively evaluated to validate their functionality and show that in many cases both the memory and speed overheads are negligible. We also discuss several use cases to illustrate the potential benefits of the proposed filters in practical applications.


翻译:过去十年来,为降低会员近似检查结构的假正率作出了重大努力,这导致开发了新的结构,如库库过滤器和xor过滤器等。最近还开发了适应性过滤器,这些过滤器可以对假正数作出反应,避免出现假正数,从而避免今后对相同要素进行查询。在本文件中,我们提议了新型静态过滤器,完全避免对特定一组负数进行假正数检查,并表明如何利用xor检验过滤器有效地实施这些过滤器。我们建议用假正数自由设置来尽量减少错误正数过滤器的内存和速度,避免假正数,从而尽量减少内存和速度管理器。已经对拟议的过滤器进行了广泛评估,以验证其功能,并表明在许多情况下,记忆和速度管理器都微不足道。我们还讨论了一些使用案例,以说明拟议过滤器在实际应用中的潜在好处。

0
下载
关闭预览

相关内容

专知会员服务
17+阅读 · 2020年9月6日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
已删除
inpluslab
8+阅读 · 2019年10月29日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
学术会议 | 知识图谱顶会 ISWC 征稿:Poster/Demo
开放知识图谱
5+阅读 · 2019年4月16日
LibRec 精选:近期15篇推荐系统论文
LibRec智能推荐
5+阅读 · 2019年3月5日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Arxiv
0+阅读 · 2022年1月13日
Arxiv
0+阅读 · 2022年1月13日
Arxiv
0+阅读 · 2022年1月13日
Arxiv
6+阅读 · 2021年6月24日
Arxiv
6+阅读 · 2019年11月14日
VIP会员
相关资讯
已删除
inpluslab
8+阅读 · 2019年10月29日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
学术会议 | 知识图谱顶会 ISWC 征稿:Poster/Demo
开放知识图谱
5+阅读 · 2019年4月16日
LibRec 精选:近期15篇推荐系统论文
LibRec智能推荐
5+阅读 · 2019年3月5日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
相关论文
Arxiv
0+阅读 · 2022年1月13日
Arxiv
0+阅读 · 2022年1月13日
Arxiv
0+阅读 · 2022年1月13日
Arxiv
6+阅读 · 2021年6月24日
Arxiv
6+阅读 · 2019年11月14日
Top
微信扫码咨询专知VIP会员