Skip to main content

Java: BloomFilter Benchmark

Intro

Bloom filter is a probabilistic data structure for searching element in a data set.
It is similar to HashSet, similarly it tells us whether the set contains certain element or not. Difference is the output of contains(element)=TRUE is futuristic.
In our example we set futuristic value to 0.01, which means the answer "It contains" is 99% correct.
Read more about Bloom filter from here: https://en.wikipedia.org/wiki/Bloom_filter

Scenario

We create two Arrays of random elements. Elements count in each array is 1,000,000.
Then we insert the first array into BloomFilter, and we iterate the first array and check if the item contains in BloomFilter. Second array is used only for checking non-existing elements.
We do the same for HashSet as described above.

Benchmarking code

We used customized version of Bloom filter  which can accept byte array.
(Previous version of this blog was using encoding of string for every put and contains, which was misguiding the performance of bloom filter)

source code:
(Source code is not organized for compilation, please modify it for your use)

Performance output:

Output
Testing BloomFilter  1000000 elements
add(): 0.176s, 5681818.181818183 elements/s
contains(), existing: 0.171s, 5847953.216374269 elements/s
Testing HashSet  1000000 elements
add(): 0.181s, 5524861.878453039 elements/s
contains(), existing: 0.08s, 1.25E7 elements/s

Memory size:


BloomFilter is the winner here. With 99% correctness the memory footprint is almost 40 times smaller than HashSet.


If we reduce correctness to 90%, then the memory footprint is reduced to 80 times.

Conclusion

We saw that BloomFilter as fast as HashMap. However, it is very space efficient.
If we have a list of URLs in HashMap in Memory, By using BloomFilter we can reduce it to 40 times. For example, if occupied memory is 500 Mb it can be reduced to 12 Mb with correctness of 99%

Comments

Popular posts from this blog

Three essential things to do while building Hadoop environment

Last year I setup Hadoop environment by using Cloudera manager. (Basically I followed this video tutorial :  http://www.youtube.com/watch?v=CobVqNMiqww ) I used CDH4(cloudera hadoop)  that included HDFS, MapReduce, Hive, ZooKeeper HBase, Flume and other essential components. It also included YARN (MapReduce 2) but it was not stable so I used MapReduce instead. I installed CDH4 on 10 centos nodes, and I set the Flume to collect twitter data, and by using "crontab" I scheduled the indexing the twitter data in Hive. Anyways, I want to share some of my experiences  and challenges that I faced. First, let me give some problem solutions that everyone must had faced while using Hadoop. 1. vm.swappiness warning on hadoop nodes It is easy to get rid of this warning by just simply running this shell command on nodes: >sysctl -w vm.swappiness=0 More details are written on cloudera's site 2. Make sure to synchronize time on all nodes (otherwise it will give error on n

NLP for Uzbek language

    Natural language processing is an essential tool for text mining in data analysis field. In this post, I want to share my approach in developing stemmer for Uzbek language.      Uzbek language is spoken by 27 million people  around the world and there are a lot of textual materials in internet in uzbek language and it is growing. As I was doing my weekend project " FlipUz " (which is news aggregator for Uzbek news sites) I stumbled on a problem of automatic tagging news into different categories. As this requires a good NLP library, I was not able to find one for Uzbek language. That is how I got a motive to develop a stemmer for Uzbek language.       In short,  Stemming  is an algorithm to remove meaningless suffixes at the end, thus showing the core part of the word. For example: rabbits -> rabbit. As Uzbek language is similar to Turkish, I was curious if there is stemmer for Turkish. And I found this: Turkish Stemmer with Snowball.  Their key approach was to u

NAT Traversal or how to make P2P on Android

Many of us used BitTorrent(or uTorrent) to download files on internet in a short time. Their download speed is high due to Peer-to-peer technology. That means, rather than downloading file from server, we are getting the file from another computer. But how two computers that have a local IP and are behind NAT, how they can connect each other? For that, NAT Traversal methodologies come for help. Note that there are mainly 2 types of NAT: Symmetrical(complex NATs:carrier-grade NAT) and Full (home network or small enterprises). let us consider Full NATs first. Methodologies of NAT traversal are: UPnP - old and hardware oriented method NAT-PMP (later succeeded by PCP)- introduced by Apple, also hardware oriented(i.e: not all routers have it, and even if it had, it is turned off by default) UDP Punching  - this is done by STUN which uses public server to discover NAT public IP & port TCP Punching -  similar to UDP punching but more complicated Symmetrical NATs are a big is