Bloom Filters: A Powerful Tool

Bloom Filters: A Powerful Tool:

Bloom Filters: A Powerful Tool By Peter Cooper / September 11, 2007 (credit: image source ) BloomFilter is a new Ruby library (available as a gem - gem install bloomfilter ) by Bryan Duxbury that provides operations to create and query "bloom filters ", an extremely space-efficient "probablistic data structure" that makes it quick and easy to test set membership. This all sounds incredibly geeky and uninteresting until you discover how bloom filters can be used to make things like ultra-fast, low-overhead spell checkers, spam filters , stop word removers, and other tools that require checking two sets of data against each other. Bryan's use for bloom filters (and BloomFilter) was to search a big list of 500 million hashes against a set of 40 million hashes. Given the size of each hash, coupled with the large quantity, a major, memory hungry task was looming. Bloom filters ...

Full article: http://www.rubyinside.com/bloom-filters-a-powerful-tool-5...