1. Bloom Filters

Background

Say a large set of structured data, each record identified by an ID, sits spread across many data files. Given a record ID, which file holds it? Reading every file to find out would be slow, and it means pulling a lot of data off disk for nothing.

One answer is an index, a separate file that maps each record ID to its offset in the data file. Sort that index file by record ID, and a lookup becomes a binary search. That works, but can we do better?

Definition

Use Bloom filters to quickly find if an element might be present in a set.