Create an Account
username: password:
 
  MemeStreams Logo

The Bloom filter

search

possibly noteworthy
Picture of possibly noteworthy
My Blog
My Profile
My Audience
My Sources
Send Me a Message

sponsored links

possibly noteworthy's topics
Arts
Business
Games
Health and Wellness
Home and Garden
Miscellaneous
  Humor
Current Events
  War on Terrorism
Recreation
Local Information
  Food
Science
Society
  International Relations
  Politics and Law
   Intellectual Property
  Military
Sports
Technology
  Military Technology
  High Tech Developments

support us

Get MemeStreams Stuff!


 
The Bloom filter
Topic: Technology 7:23 am EDT, Apr 17, 2008

The Bloom filter, conceived by Burton H. Bloom in 1970, is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positives are possible, but false negatives are not. Elements can be added to the set, but not removed (though this can be addressed with a counting filter). The more elements that are added to the set, the larger the probability of false positives.

For example, one might use a Bloom filter to do spell-checking in a space-efficient way. A Bloom filter to which a dictionary of correct words has been added will accept all words in the dictionary and reject almost all words which are not, which is good enough in some cases. Depending on the false positive rate, the resulting data structure can require as little as a byte per dictionary word.

In the last few years Bloom filter become hot topic again and there were several modifications and improvements. In this talk I will present my last few improvements in this topic.

The Bloom filter



 
 
Powered By Industrial Memetics
RSS2.0