算法与理论计算机2020arxiv.org
年龄分区布隆过滤器（Age-Partitioned Bloom Filters）
Age-Partitioned Bloom Filters
进阶 · 约 60 分钟读完前置知识：布隆过滤器基础、概率与信息论基础
导读
这篇论文提出 Age-Partitioned Bloom Filters（APBF），一种按时间分区的布隆过滤器变体，用于解决传统布隆过滤器无法高效处理“最近插入的元素”这类带时效性的成员查询问题。通过按年龄分区并逐步衰减旧条目，它能在保证查询性能的同时自动淘汰过期数据。
HN 关注点：布隆过滤器是工程中常用的基础数据结构，HN 读者关注这种改进变体的实际应用价值，以及它与大家各自“自己发明”的滚动/时效性布隆过滤器方案的异同。
HN 评论精选
这几条评论里：支持 1 补充 1 亲历 2
亲历分享 Reddit 用布隆过滤器+时间戳优化投票查询的亲历经验
先科普一下：布隆过滤器非常擅长判断“某元素不在集合中”——当它说不存在时是 100% 准确且极快的。我们在 Reddit 就利用了这一点：加载评论页时需要判断你是否对任何评论投过票，把布隆过滤器放在前面，如果答案是“没投过”，查询就非常快。但我们仍需发起查询，所以又加了个技巧：在用户对象上记录你最后一次访问网站的时间，如果评论页创建于那之后，连查询都不用发。有了这篇论文的方案，或许就不需要这两步流程了——在有时间限制的场景下应该会非常快。也许吧。
jedberg查看英文原文
This is really great! For those that don't know, bloom filters are really good at determining when something is not in a set. So if says "not in set" that's 100% accurate and super fast. We used this to our advantage at reddit. When you load a comments page, we had to determine if you've voted on anything. So with the bloom filter in front, the query for "have they voted on anything here" was very quick if the answer was no. But we still had to make the query. So another hack we did was to put a value on your user object to track the last time you interacted with the website. If the comments page was made after your last interaction, then we didn't even have to do the query. With this, we wouldn't have to do the two step process -- it sounds like this would be super fast when it was time boxed. Maybe...
亲历指出自己项目里独立实现过类似的滚动布隆过滤器，并附上代码
Aether（https://getaether.net）也一直在用一种大致等价的方案。我之前还以为自己‘发现’了它，称之为‘Rolling Bloom’（不确定谁的实现更早）。这是 Go 实现：https://github.com/nehbit/aether/aether-core/aether/services/rollingbloom/rollingbloom.go
rolleiflex查看英文原文
Aether (https://getaether.net) also uses a roughly equivalent version of this I had thought, up to this point, that I ‘discovered’. I call it ‘Rolling Bloom’. (Not sure which implementation is first.) Here’s the Go implementation: https://github.com/nehbit/aether/blob/master/aether-core/aether/services/rollingbloom/rollingbloom.go
支持证实自己也在认证场景中用过类似结构，肯定论文的系统性分析
我以前用过类似的东西，感谢你们把它系统性地刻画出来。我用它是做认证拒绝（authentication rejection）的。
microcolonel查看英文原文
I've used something like this before, thank you for characterizing it. :- ) I used mine for authentication rejection.
补充玩谐音梗调侃论文标题
错过了一个好机会——这篇论文应该叫 "OK Bloomer"。
stupidcar查看英文原文
Missed opportunity to title this paper "OK Bloomer".
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2020Hacker News 讨论帖141 分 · 11 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选