Bloom filter: a standalone construct

Burton H. Bloom introduced this data structure in 1970 in Communications of the ACM, where he showed how to test whether an item belongs to a set while using far less memory than storing the set itself. A Bloom filter is a fixed array of bits together with several hash functions, which are procedures that map an item to positions in the array; to add an item its hash positions are set to 1, and to query an item those same positions are checked. If any of those positions is 0 the item is definitely not in the set, and if all of them are 1 the item is probably in the set, so the structure can return a false positive but never a false negative. Andrei Broder and Michael Mitzenmacher's 2004 survey in Internet Mathematics collected the many networking and systems uses that grew from Bloom's idea and serves as a standard modern reference. What makes the Bloom filter a landmark is that it trades a tunable, quantifiable error rate for a large and predictable saving in space, with its size set by the number of items and the target error rate rather than by the size of the items themselves.[1][2]

Unit

A bit array plus several independent hash functions, sized by the number of items and the target false-positive rate

Recovery means

Not applicable

Measured by

Characterised by its false-positive probability as a function of the bit-array size, the number of hash functions, and the number of inserted items