为什么布隆过滤器被称为“过滤器”？

Question

为什么布隆过滤器被称为“过滤器”。它们的行为更像集合，或者至少是可以查询成员资格的匿名集合。过滤器在其中起了什么作用？

Answer 1

布隆过滤器被称为过滤器，因为它们通常被用作廉价的第一次通过，以过滤出与查询不匹配的数据集的片段。

在the ACM database中，对标题为“布隆过滤器”的论文的最早引用是：

LeeL.Gremilm，为差分文件访问设计布隆过滤器，ACM通信，v.25 n.9，第600-604页，1982年9月

数据库中对摘要中包含Bloom Filter的论文的最早引用是：

从1978年开始发表的“关于差异文件在计算机辅助设计中的应用的说明”。

有一些早期的论文被列为引用了原始论文，但没有一篇论文在摘要中引用它，全文在付费墙后面。

Answer 2

Bloom filters回答集合成员关系查询时会出现片面错误:它们可能会回答您的元素不是集合的成员，或者它可能是集合的成员。这与set数据结构不同，set数据结构可以精确地回答成员查询。在一个典型的应用程序中，你有一个查询成本很高的集合结构和一个布隆过滤器。你查询bloom过滤器，如果它说“不是成员”，你相信它。如果它说“可能”，你可以查询集合。