“I haven't fully read the paper yet, but it seems like a variation of a bloom filter”
Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters
提出 xor 过滤器,近似集合成员查询更快且更省空间
论文实现并实测了 Dietzfelbinger 和 Pagh 提出的一种基于 Bloomier 过滤器的近似成员查询结构,称为 xor 过滤器。结果显示它可以比 Bloom 和 cuckoo 过滤器更快,同时占用更少内存。更紧凑的 xor+ 版本比 Golomb 压缩序列等高度紧凑的方案占用更少空间,速度仍可与 Bloom 过滤器媲美。
HN 评论者把它当作 Bloom / Cuckoo 过滤器的更优替代品来推荐,并讨论其与完美哈希的相似之处,有人在基准里看到差距大约是 2 倍。
学习路径
读这篇之前,按顺序读书架上的 1 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出候选里只有一篇 Bloom 过滤器的扩展论文与目标论文主题相关,其余是不相关的随机数论文,所以只列相关的一篇再接目标论文。
- 1
同样是 Bloom 过滤器相关的工作,说明这类近似成员查询结构的使用场景。
读基本 Bloom 过滤器如何工作,以及多过滤器索引要解决什么问题;不用细看 B+ 树细节。
- 2Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters
目标论文:以 Bloomier 过滤器为基础提出 xor 过滤器,比 Bloom 与 Cuckoo 过滤器更快更省空间。
读xor 过滤器的构造与查询过程,以及与 Bloom、Cuckoo 在空间和速度上的对比。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“the XOR filter description starts at page 3.”
“Or you go with Xor filters, which are more efficient than both Cockoo and Bloom filters.”
“the xor filter paper, the difference is _much_ smaller; maybe factor 2”
“I did find this Xor Filters which may or may not be related.”