Inproceedings,
Network Applications of Bloom Filters: A Survey
Internet Mathematics, 1, page 636--646. (2002)
Abstract
A Bloom filter is an ingenious randomized data-structure for concisely
representing a set in order to support approximate membership queries.
The space efficiency is achieved at the cost of a small probability
of false positives. It was invented by Burton Bloom in 1970 for the
purpose of spell checking and for many years it was seldom mentioned
in other contexts, except for database optimization. Nevertheless,
Bloom&\#039;s beautiful approach has seen a sudden resurgence in
a variety of large-scale network applications such as shared web
caches, query routing, and replica location. This survey presents
a plethora of recent uses of this old data structure, its modern
variants, and the mathematical basis behind them, with the aim of
making these ideas available to a wider community and the hope of
inspiring new applications.
