Bloom Filter

The Bloom filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positives are possible, but false negatives are not. Elements can be added to the set, but not removed (though this can be addressed with a counting filter). The more elements that are added to the set, the larger the probability of false positives.

Practical applicaitons of Bloom filter including fast test that whether a request could be handled by a server instance, whether a data element is in a replicate in a redundent system.