Bloom Filters in Tcl
Written by Wojciech Kocjan   
Recently I've been playing around with Bloom Filters and wrote a quick implementation in Tcl. After seeing how easy it is, I've decided to show the code to a wider audience.

Bloom Filters are a data structure that uses a constant size in order to store information about elements in a set. It allows adding elements to the set and querying if an element is in a set. Bloom Filters work in such a way that false positives can occur, but false negatives cannot. It means that if you query it for a particular element, the result can be that it's very probably an element is in a set or it's definitely not in a set. Mathematical model describes exactly how to calculate probability of false positives, as well as gives methods to calculate size of bloom filter and number of hashes to generate in order to get proper false positive probability rate for a specified number of elements.

For more information about Bloom Filters, please visit Bloom Filters on Wikipedia.

Bloom Filters are mainly effective in data synchronization where sending actual data to compare takes a lot of bandwidth and/or the data can be sensitive - such as synchronizing contact list in IM application. The idea is that one side (usually server) is able to determine which elements the other side has without sending the elements themselves. This algorithm works regardless of actual element size, and size of Bloom Filter required to gain assumed accuracy does not depend on element size.

The idea of a bloom filter is simple - storage of current state is a series of bits (m bits). Adding an element to a set implies enabling several bits if they are not already set, and querying if an element is in a set means checking if all bits are set. Mapping between each element and bits that represent it is done by calculating k number of hash values of that element. This means that each element is represented by a m bit integer number with k bits set. Each bit is chosen as result of calculating a hash modulo number of bits.

A very important thing is that each hash value has to be independant from other hash values. My implementation uses HMAC from either MD5 or SHA1 to achieve this. Value for key is the number of current hash calculated. The code below illustrates this:

Generating hashes for Bloom Filters
namespace eval bloomfilter {}

# Tcl 8.5 is needed since we're using bignum
package require Tcl 8.5

proc bloomfilter::generateHashes {algorithm m k data} {
    package require $algorithm
    set rc 0
    set bitlist {}
    set key 0
    while {[incr k -1] >= 0} {
        if {[llength $bitlist] == 0} {
            binary scan [${algorithm}::hmac -key [incr key] $data] I* bitlist
        }

        set bit [expr {[lindex $bitlist 0] % $m}]
        set bitlist [lrange $bitlist 1 end]
        set rc [expr {$rc | (2<<$bit)}]
    }
    return $rc
}

This code loops until k hashes have been generated. It calculates HMAC and splits the result into discrete 32-bit representations, which are then mapped to bits, by calculating them modulo m. If this is a previous iteration or list of bits from previous hash calculations is empty, a hash is calculated and split into 32 bit integers by binary scan. Then first element from that list is taken, removed from the list and added to result as 2 << $bit.

This is the basic of our Bloom Filter implementation. Next we can create 4 procedures - to initialize a bloom filter storage, clean up a storage, to add an element and to query if an element is present in a set. Let's start with initialization and cleanup:

Initialize and finalize a Bloom Filter set
proc bloomfilter::init {algorithm n {m ""} {k ""}} {
    set name "::bloomfilter::set[incr ::bloomfilter::setCounter]"

    if {$m == ""} {
        set m [expr {int($n * 9.6)}]
    }
    if {$k == ""} {
        set k [expr {int(log(2) * ($m / $n))}]
    }

    upvar #0 $name v
    set v(value) 0
    set v(algorithm) $algorithm
    set v(n) $n
    set v(m) $m
    set v(k) $k

    return $name
}

proc bloomfilter::finalize {n} {
    unset $n
}

Our set uses an array to store all information. Algorithm can be either md5 or sha1. Implementation uses hmac commands from respective packages for calculating hashes.

The n variable specifies how many items should the set be able to manage - it is mainly used if m and k are not specified - then m is calculated to offer 1% false positive probability. If k is not specified, it is calculated to use optimum number of hashes, based on algorithm described in the Wikipedia. If all three values are provided, n is not really used for anything.

Next, let's add commands for adding and querying data.

Adding and querying an element
proc bloomfilter::add {name data} {
    upvar #0 $name v
    set v(value) [expr {$v(value) | [generateHashes $v(algorithm) $v(m) $v(k) $data]}]
}

proc bloomfilter::query {name data} {
    upvar #0 $name v

    set hashes [generateHashes $v(algorithm) $v(m) $v(k) $data]

    return [expr {($v(value) & $hashes) == $hashes}]
}

Implementation is really trivial - adding does an OR operation of current value and bitmask of newly added element. Querying is also trivial - it is just checking if all bits that this element maps to are set in current value.

Sample test
set n [bloomfilter::init 5]

bloomfilter::add $n "test1"
bloomfilter::add $n "test2"
bloomfilter::add $n "test3"
bloomfilter::add $n "test5"
bloomfilter::add $n "test7"

puts [bloomfilter::query $n "test1"]
puts [bloomfilter::query $n "test2"]
puts [bloomfilter::query $n "test3"]
puts [bloomfilter::query $n "test4"]
puts [bloomfilter::query $n "test5"]
puts [bloomfilter::query $n "test6"]
puts [bloomfilter::query $n "test7"]

bloomfilter::finalize $n
Most probably example above would return 1,1,1,0,1,0,1 lines.

For more detailed tests, I put a list of 22000 strings into a Bloom Filter, queried it against 52000 strings and received only one false positive (0.1%) when using 14.4 bits per item - so I'd need around 40k to send/receive a Bloom Filter to compare sets of 22000 elements with 0.1% false positive ratio.