统计

留言簿(1)

DB

Others

QA

Tech Website

阅读排行榜

评论排行榜

Bloom Filter

#Algorithm description:
The Bloom filter, conceived by Burton Howard 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 positivesare 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.
An empty Bloom filter is abit array of m bits, all set to 0. There must also be k different hash functions defined, each of which maps or hashes some set element to one of them array positions with a uniform random distribution.

#Bloom Filter's Principle:


An example of a Bloom filter, representing the set {x, y,z}. The colored arrows show the positions in the bit array that each set element is mapped to. The element w is not in the set {x, y, z}, because it hashes to one bit-array position containing 0. For this figure, m=18 and k=3.

#Bloom Filter Application

Google BigTable uses Bloom filters to reduce the disk lookups for non-existent rows or columns. Avoiding costly disk lookups considerably increases the performance of a database query operation.[2]

The Squid Web Proxy Cache uses Bloom filters for cache digests.[3]

The Venti archival storage system uses Bloom filters to detect previously-stored data.[4]

The SPIN model checker uses Bloom filters to track the reachable state space for large verification problems.[5]

The Google Chrome web browser uses Bloom filters to speed up its Safe Browsing service.[6]


Read more:http://www.answers.com/bloom%20filter

posted on 2011-06-12 23:58 XXXXXX 阅读(290) 评论(0)  编辑  收藏 所属分类: Algorithm


只有注册用户登录后才能发表评论。


网站导航: