- Bloom filter; a space-efficient probabilistic data structure that is used to test whether an element is a member of a set^[https://en.wikipedia.org/wiki/Bloom_filter]
- false positive matches are possible, but false negatives are not – in other words, a query returns either "possibly in set" or "definitely not in set"
- e.g. Google indexing URLs^[Algorithms to Live By: The Computer Science of Human Decisions, p. 205]
- [[algorithm]]