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

Taught in

References