按年被提到
20222022 · 2 次2026
算法与数据结构›经典算法与数据结构·arXiv:2201.01174 · cs.DS

Binary Fuse Filters: Fast and Smaller Than Xor Filters

二元融合过滤器:比 Xor 过滤器更快更小
Thomas Mueller Graf, Daniel Lemire · 2022

提出二元融合过滤器,存储逼近理论下限且构建更快

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 5 人首次 2022-01-08 · 最近 2026-01-17
5不同的人
5活跃月份
5讨论串
28被引(OpenAlex)

Xor 过滤器的存储量在理论下限的 23% 以内,而 Bloom 过滤器是 44%。受 Dietzfelbinger 与 Walzer 启发,论文构建了二元融合过滤器(binary fuse filter),存储在下限的 13% 以内且不牺牲查询速度,构建速度还可以比 xor 过滤器快一倍以上;稍微牺牲查询速度,可进一步把存储降到下限的 8% 以内。作者与 Bloom、分块 Bloom、向量商过滤器、cuckoo 和 ribbon 过滤器等方案比较,实验表明二元融合过滤器优于 xor 过滤器。

HN 为什么提它

HN 评论者提到它多半是作为 xor 过滤器的改进版来引用,例如指出论文含有与 Ribbon 过滤器的比较,或说明自己在实现中配合基数排序使用。

方法难度 3 / 5约 35 分钟经得起时间
读之前最好知道
1Bloom 过滤器与近似成员查询
2xor 过滤器
3哈希函数与哈希表
4信息论下限(空间下界)

学习路径

读这篇之前,按顺序读书架上的 2 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出

候选里和二元融合过滤器直接相关的是 Xor 过滤器和 Ribbon 过滤器,读完能看清近似集合成员过滤器在空间与速度上的演进。

  1. 1
    Xor Filters: Faster and Smaller Than Bloom and Cuckoo FiltersXor 过滤器:比 Bloom 和 Cuckoo 过滤器更快更小 · 2019

    二元融合过滤器是对 Xor 过滤器的直接改进。

    读Xor 过滤器的构造(三个哈希、剥离)与空间开销。

  2. 2
    Ribbon filter: practically smaller than Bloom and XorRibbon 过滤器:实用上比 Bloom 和 Xor 更小 · 2021

    同期的另一种更小的静态过滤器,可对比空间与构建速度。

    读空间开销与查询、构建代价的权衡。

  3. 3
    Binary Fuse Filters: Fast and Smaller Than Xor Filters二元融合过滤器:比 Xor 过滤器更快更小 · 2022 · 就是这篇

    目标论文:存储更接近理论下限且构建更快的过滤器。

    读融合图的构造、与 Xor 过滤器的差别,以及空间与速度对比。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用Genbox · 2022-10

“The paper includes comparisons with Ribbon filter”

指出这篇论文包含与 Ribbon filter 的对比
Cuckoo Filter: Practically Better Than Bloom (2014) [pdf]原评论 ↗
引用thomasmg · 2024-09

“We have used radix sorting for the binary fuse filter Binary Fuse Filters.”

说明自己团队在 binary fuse filter 中使用了基数排序
When Bloom filters don't bloom (2020)原评论 ↗
被提交为 story · 3 次