Understanding Bloom Filters with Pharo Smalltalk

Tags: #data-structures , #moldable-development , #osoco , #pharo y #smalltalk

A Bloom filter is a space-efficient data structure, conceived by Burton Howard Bloom in 1970 (Space/Time Tradeoffs in Hash Coding with Allowable Errors), that represents a set of elements and allows you to test if an element is a membership. For example, consider the element , whose 4 hash values collision in the bit 36 that is already set in our filter example, so the method concludes the element may exist in the filter:

As we have shown, Bloom filters can lead to situations where some element is not a member, but the algorithm returns it might be. Fortunately, a Bloom filter has a predictable false positive probability ( ):

Our implementation is built specifying the estimated number of elements to be added ( ) and the false positive probability ( ), then the data structure uses the previous formula to compute the optimal number of hashes and bit array length.

Source: osoco.es