Skip to main content

“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



Popular posts from this blog

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

Recently I found this issue while writing code snippet in "JSFiddle". And after searching, found this was happening because of new feature added in "Chrome 46+". But at the same time Chrome doesn't have support for "allow-modals" property in "sandbox" attribute.

Chromium issue for above behavior:
https://codereview.chromium.org/1126253007

To make it work you have to add "allow-scripts allow-modals" in "sandbox" attribute, and use "window.alert" instead of "alert".



<!-- Sandbox frame will execute javascript and show modal dialogs --> <iframe sandbox="allow-scripts allow-modals" src="iframe.html"> </iframe>


Feature added: Block modal dialog inside a sandboxed iframe.
Link: https://www.chromestatus.com/feature/4747009953103872

Feature working Demo page:
https://googlechrome.github.io/samples/block-modal-dialogs-sandboxed-iframe/index.html



CSS Specificity

Many time different CSS rules overlap on one or more element. And some people always get confuse about, which rule will take higher priority then other and why? CSS Specificity is the answer of all these kind of questions.
As the name suggest, the CSS rule which is more specific to the element will take higher priority then other. Means something like “#some_id{}” will always take higher priority then “*{}” universal selector.  And if duplicate rules are define then the last rule will be applied to the element.

The following list of selectors is by increasing specificity:
Type selector (e.g., div) and pseudo-elements in selector (e.g., :after) Class selectors (e.g., .some_class), attributes selectors (e.g., [type=”radio”]) and pseudo-class selector (e.g., :hover) Id selectors (e.g., #some_id)


ID takes higher priority then Class, Type and Universal selector (Note: Universal selector has no effect on specificity, see below special conditions). 



If duplicate rules are given, then last…

Guava: Some useful IO utilities

Guava IO package provides very useful utility classes for input/ouput stream, byte stream, file handling and many more. Here are few example which show case how these utilities can make your code much cleaner, modular and more readable.Copy “InputStream” to “OutputStream InputStream is = CopyStreams.class.getResourceAsStream("test.txt"); OutputStream os = System.out; ByteStreams.copy(is, os);Changing InputStream to “byte[]” InputStream is = CopyStreams.class.getResourceAsStream("test.txt"); byte[] isBytes = ByteStreams.toByteArray(is); // Now if you want to get base64 encoded string then it will be like this String isBase64Str = new sun.misc.BASE64Encoder().encode(isBytes);Combining two files in one File input1 = new File("c:\\testio\\AWords.txt"); File input2 = new File("c:\\testio\\BWords.txt"); File output = new File("c:\\testio\\ABWords.txt"); …