fridgebuzz

“A Bloom filter is a simple space-efficient randomized data-structure for representing a set in order to support membership queries.” The survey paper Network Applications of Bloom Filters is a great technical overview of what they are and what you might want to use them for. Examples include distributed caching, distributed hash tables (DHTs), resource routing, more efficient multicast, and traffic measurement. For a quickstart, see this helpful tutorial on using Bloom filters in place of lookup hashes in Perl. The author also describes how Bloom filters may be applied in social software systems to allow people to share information about their networks without revealing who their friends are to the world or to a central authority.