“Bloom Filter” to optimize expensive data lookups


Bloom Filter is very useful when you want to optimize the functionality with following constraints
  1. Data lookup is very expensive
  2. False positive is acceptable and
  3. False negative is un-acceptable

A 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 positive retrieval results are possible, but false negatives are not; i.e. a query returns either "inside set (may be wrong)" or "definitely not in set".wikipedia.org
 360px-Bloom_filter_speed.svg

It stores only value hash in it’s data structure, so it take very less memory against the very huge data.
For example if you have set of raw data with
  • 107 elements
  • 105 distinct value
  • and size ~40MB
Bloom filter will store same data as hash in just ~0.6MB. (ref.)
And because of the same reason it is quite fast.

Bloom Filter implementation
Guava library has bloom filter implementation
.Net implementation

Bloom Filter In Use
  1. Chrome uses Bloom filters to make a preliminary decision whether a particular web site is malicious or safe.
  2. Google Big table uses it to reduce disk lookups
  3. Squid Web Proxy Cache uses Bloom filters for cache digests
  4. Cassandra uses to save IO when performing a key lookup

Useful links
Bloom filter by example
Space-Efficient Bloom Filters
"More Optimal Bloom Filters," Ely Porat (Nov/2007) Google TechTalk video on YouTube



Comments

Popular posts from this blog

ERROR: Ignored call to 'alert()'. The document is sandboxed, and the 'allow-modals' keyword is not set.

CSS Specificity

Application Design Notes