“This paper does a good job of showing the space/time tradeoffs of various approximate sets.”
Ribbon filter: practically smaller than Bloom and Xor
新型静态集合过滤器 Ribbon,空间开销可低于 10%
过滤器近似表示键集合,误报率为 f 时每个键至少需要 log2(1/f) 比特,而现有实用过滤器在 f≥2^-4 时至少有 20% 的空间开销。Ribbon 过滤器面向静态集合,空间开销与误报率可大范围配置且速度有竞争力:许多情况下同样空间开销下更快,或以额外 CPU 时间把开销压到 10% 以下,带负载均衡的实验设计甚至低于 1%。它类似为局部性优化的 Xor 过滤器,通过解带状布尔线性方程组构造,论文还给出更快的求解过程和多项实用增强。
评论者把它当作比 Bloom 过滤器更紧凑的近似集合结构的代表,并称赞它清晰展示了各类近似集合的空间与时间权衡。
学习路径
读这篇之前,按顺序读书架上的 2 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出候选里只有 Xor 过滤器与目标直接相关,加上一篇与哈希到区间映射相关的论文,这条路径帮你建立静态近似集合过滤器的背景。
- 1
哈希值映射到区间的快速方法(fastrange 一类思路),过滤器实现常用。
读用乘法加移位代替取模把随机整数映射到区间的思路,了解即可。
- 2
Ribbon 的直接对比对象:同为静态集合的 Bloom 替代方案,Ribbon 想进一步压缩空间。
读Xor 过滤器的构造方式、空间开销与速度,以及它与 Bloom、Cuckoo 过滤器的比较。
- 3Ribbon filter: practically smaller than Bloom and Xor
目标论文:空间开销可低于 10% 的新型静态过滤器。
读空间开销与假阳性率的关系、与 Bloom 和 Xor 的对比,以及构造和查询的基本思路。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“The forefront of CRL design is in set compression techniques like Ribbon filters Ribbon filter”
“Also quite recent are Ribbon filters: Ribbon filter”
“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.”
- Ribbon filter: practically smaller than Bloom and Xor ↗ot · 2021-03-05 · 2 分
- Ribbon filter: practically smaller than Bloom and Xor ↗harporoeder · 2021-07-12 · 1 分