Counting Bloom Filter implemented in Ruby.
Bloom filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positives are possible, but false negatives are not. For more detail: en.wikipedia.org/wiki/Bloom_filter
Performance of the Bloom filter depends on a number of variables:
-
size of the bit array
-
size of the counter bucket
-
number of hash functions
To figure out the values for these parameters, refer to:
To learn about applications and reasons for the time based bloom filters, refer to:
Instead of using k different hash functions, this implementation seeds the CRC32 hash with k different initial values (0, 1, …, k-1). This may or may not give you a good distribution, it all depends on the data.
require 'bloomfilter' bf = BloomFilter.new(:size => 100, :hashes => 2, :seed => 1, :bucket => 3, :raise => false) bf.insert("test") bf.include?("test") => true bf.include?("test2") => false bf.delete("test") bf.include?("test") => false # Hash with a bloom filter! bf["test2"] = "bar" bf["test2"] => "bar" bf["test3"] => nil bf.stats Number of filter bits (m): 10 Number of filter elements (n): 2 Number of filter hashes (k) : 2 Predicted false positive rate = 10.87%
bf = BloomFilter.new(:type => :redis, :ttl => 2, :server => {:host => 'localhost'}) bf.insert('test') bf.include?('test') => true sleep(2) bf.include?('test') => false
Tatsuya Mori <[email protected]> (Original C implementation: vald.x0.com/sb/)