Bloom Filter

A Bloom filter is a compact probabilistic structure for testing whether an item may belong to a set. A standard correctly maintained filter can report false positives but not false negatives.

A definite absence can therefore avoid a costly storage lookup, while a possible presence still needs verification. Its memory size and number of hash functions affect the false-positive rate. Ordinary Bloom filters do not support safe arbitrary deletion without an adapted design.