按年被提到
20212021 · 2 次2026
算法与数据结构›哈希、压缩与向量化·arXiv:2103.02515 · cs.DS

Ribbon filter: practically smaller than Bloom and Xor

Ribbon 过滤器:实用上比 Bloom 和 Xor 更小
Peter C. Dillinger, Stefan Walzer · 2021

新型静态集合过滤器 Ribbon,空间开销可低于 10%

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 6 人首次 2021-03-05 · 最近 2026-01-22
6不同的人
6活跃月份
6讨论串
40被引(OpenAlex)

过滤器近似表示键集合,误报率为 f 时每个键至少需要 log2(1/f) 比特,而现有实用过滤器在 f≥2^-4 时至少有 20% 的空间开销。Ribbon 过滤器面向静态集合,空间开销与误报率可大范围配置且速度有竞争力:许多情况下同样空间开销下更快,或以额外 CPU 时间把开销压到 10% 以下,带负载均衡的实验设计甚至低于 1%。它类似为局部性优化的 Xor 过滤器,通过解带状布尔线性方程组构造,论文还给出更快的求解过程和多项实用增强。

HN 为什么提它

评论者把它当作比 Bloom 过滤器更紧凑的近似集合结构的代表,并称赞它清晰展示了各类近似集合的空间与时间权衡。

方法难度 4 / 5约 60 分钟经得起时间
读之前最好知道
1Bloom 过滤器
2Xor 过滤器
3布尔线性方程组与高斯消元
4哈希表与哈希函数

学习路径

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

候选里只有 Xor 过滤器与目标直接相关,加上一篇与哈希到区间映射相关的论文,这条路径帮你建立静态近似集合过滤器的背景。

  1. 1
    Fast Random Integer Generation in an Interval区间内的快速随机整数生成 · 2018

    哈希值映射到区间的快速方法(fastrange 一类思路),过滤器实现常用。

    读用乘法加移位代替取模把随机整数映射到区间的思路,了解即可。

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

    Ribbon 的直接对比对象:同为静态集合的 Bloom 替代方案,Ribbon 想进一步压缩空间。

    读Xor 过滤器的构造方式、空间开销与速度,以及它与 Bloom、Cuckoo 过滤器的比较。

  3. 3
    Ribbon filter: practically smaller than Bloom and XorRibbon 过滤器:实用上比 Bloom 和 Xor 更小 · 2021 · 就是这篇

    目标论文:空间开销可低于 10% 的新型静态过滤器。

    读空间开销与假阳性率的关系、与 Bloom 和 Xor 的对比,以及构造和查询的基本思路。

HN 书评

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

“This paper does a good job of showing the space/time tradeoffs of various approximate sets.”

推荐,称它清晰比较了各种近似集合结构的空间/时间权衡
Cuckoo Filter: Practically Better Than Bloom (2014) [pdf]原评论 ↗
引用doomrobo · 2022-09

“The forefront of CRL design is in set compression techniques like Ribbon filters Ribbon filter”

把 Ribbon 过滤器当作集合压缩技术的前沿
A New Life for Certificate Revocation Lists原评论 ↗
引用sparkie · 2025-05

“Also quite recent are Ribbon filters: Ribbon filter”

补充提到 Ribbon 过滤器是较新的 Bloom 过滤器替代方案
Bloom Filters原评论 ↗
引用less_less · 2026-01

“See also the paper Ribbon filter: practically smaller than Bloom and Xor: Ribbon filter, which is a similar idea though not by the same authors.”

拿它作相关参考,思路相近但作者不同
Binary Fuse Filters: Fast and Smaller Than XOR Filters原评论 ↗
被提交为 story · 2 次