probabilistic data structure
A data structure that trades a small, controllable chance of a wrong answer for large savings in memory or time.
In more detail
A Bloom filter is the classic example: its errors are only in one direction and their rate can be tuned. Such structures are used as a fast first check in front of something expensive, such as a disk read or a database query.
Related terms
- Bloom filter — A compact, probabilistic set that can say "definitely not present" or "probably present", using a bit array and several hash functions.
- false positive — A check result that claims something is true when it is not, such as a test passing on broken code or a tool flagging correct code.
Taught in
- Bloom Filters: Membership Without The Data — Algorithms & Data Structures for Working Engineers