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

Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters

Xor 过滤器:比 Bloom 和 Cuckoo 过滤器更快更小
Thomas Mueller Graf, Daniel Lemire · 2019

提出 xor 过滤器,近似集合成员查询更快且更省空间

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 5 人首次 2019-12-20 · 最近 2025-07-02
5不同的人
4活跃月份
4讨论串
139被引(OpenAlex)

论文实现并实测了 Dietzfelbinger 和 Pagh 提出的一种基于 Bloomier 过滤器的近似成员查询结构,称为 xor 过滤器。结果显示它可以比 Bloom 和 cuckoo 过滤器更快,同时占用更少内存。更紧凑的 xor+ 版本比 Golomb 压缩序列等高度紧凑的方案占用更少空间,速度仍可与 Bloom 过滤器媲美。

HN 为什么提它

HN 评论者把它当作 Bloom / Cuckoo 过滤器的更优替代品来推荐,并讨论其与完美哈希的相似之处,有人在基准里看到差距大约是 2 倍。

方法难度 3 / 5约 30 分钟经得起时间
读之前最好知道
1Bloom 过滤器
2哈希函数与哈希表
3近似集合成员查询
4算法复杂度与缓存效应

学习路径

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

候选里只有一篇 Bloom 过滤器的扩展论文与目标论文主题相关,其余是不相关的随机数论文,所以只列相关的一篇再接目标论文。

  1. 1
    Bloofi: Multidimensional Bloom FiltersBloofi:多维布隆过滤器 · 2015

    同样是 Bloom 过滤器相关的工作,说明这类近似成员查询结构的使用场景。

    读基本 Bloom 过滤器如何工作,以及多过滤器索引要解决什么问题;不用细看 B+ 树细节。

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

    目标论文:以 Bloomier 过滤器为基础提出 xor 过滤器,比 Bloom 与 Cuckoo 过滤器更快更省空间。

    读xor 过滤器的构造与查询过程,以及与 Bloom、Cuckoo 在空间和速度上的对比。

HN 书评

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

“I haven't fully read the paper yet, but it seems like a variation of a bloom filter”

没读完全文,觉得它像是 Bloom 过滤器的变体
Xor Filters: Faster and Smaller Than Bloom Filters原评论 ↗
引用_visgean · 2019-12

“the XOR filter description starts at page 3.”

指出 Xor 过滤器的描述从第 3 页开始
Xor Filters: Faster and Smaller Than Bloom Filters原评论 ↗
引用KenanSulayman · 2020-07

“Or you go with Xor filters, which are more efficient than both Cockoo and Bloom filters.”

建议改用 Xor 过滤器,比 Cuckoo 和 Bloom 都更高效
Bloom filters debunked: Dispelling 30 Years of bad math with Coq原评论 ↗
引用thomasmg · 2021-08

“the xor filter paper, the difference is _much_ smaller; maybe factor 2”

指出 Xor 过滤器论文里的差距小得多,大约两倍
Bloom Filters: More than a space-efficient hashmap原评论 ↗
引用convolvatron · 2025-07

“I did find this Xor Filters which may or may not be related.”

贴出这篇论文,不确定是否相关
Efficient set-membership filters and dictionaries based on SAT原评论 ↗