← recall

bloom filter term

probabilistic structure: 'definitely not' or 'probably yes'

Compact set membership test with false positives but no false negatives. Used in LSM trees to skip segments that definitely don't contain a key.

topics: databases, data-structures, caching

references:

• Wikipedia — Bloom filter