Why are bloom filters called “filters”?

Question

Why are bloom filters called "filters". They behave more like sets, or at least an anonymous set that can be queried for membership. Where does filter come into it?

Answer 1

Bloom filters are called filters because they are often used as a cheap first pass to filter out segments of a dataset that do not match a query.

The earliest reference in the ACM database to a paper with "Bloom Filter" in its title is:

Lee L. Gremillion, Designing a Bloom filter for differential file access, Communications of the ACM, v.25 n.9, p.600-604, Sept 1982

The earliest reference in the database to a paper with Bloom Filter in its abstract is:

"A note on the application of differential files to computer aided design" from 1978.

There are earlier papers that are listed as citing the original paper, but none of them cite it in their abstracts and the full texts are behind a pay wall.

Answer 2

Bloom filters answer set membership queries with one-sided error: They can reply that your element is not a member of the set, or that it may be a member of the set. This is different from a set data structure, which can answer membership queries precisely. In a typical application, you have a set structure which is costly to query and a bloom filter in addition. You query the bloom filter, if it says "not member" you believe it. If it says "maybe", you query the set.