bloem

Bloem implements three Bloom Filters for node.js. All use the FNV Hash function and the optimization described in 1 by Kirsch and Mitzenmacher.

• Bloem, a classic bloom filter dimensioned by the size of the bitfield and the number of hash functions
• SafeBloem, enforces a given false positive error probabilty for a given capacity
• ScalingBloem, a scaling bloom filter (SBF) as described by Almeida et al. in 2

Install

npm install bloem

Usage

Bloem

var bloem = require('bloem')
var filter = new bloem.Bloem(16, 2)
filter.has(Buffer("foobar")) // false
filter.add(Buffer("foobar"))
filter.has(Buffer("foobar")) // true
filter.has(Buffer("hello world")) // false

SafeBloem

var bloem = require('bloem')
var filter = new bloem.SafeBloem(2, 0.1)
filter.add(Buffer("1")) // true
filter.add(Buffer("2")) // true
filter.add(Buffer("3")) // false

filter.has(Buffer("3")) // false
filter.has(Buffer("1")) // true

API

Class: Bloem

new Bloem(size, slices)

• size Number - bits in the bitfield
• slices Number - how many hashfunctions to use

Create a new Bloem filter object.

filter.add(key)

• key Buffer - key to add

Add a key to the set

filter.has(key)

• key Buffer

Test if key is in the set

Class: SafeBloem

new SafeBloem(capacity, errorrate)

• capacity Number - capacity of the filter
• errorrate Number

Create a new bloom filter that can hold capacity elements with an error probability of errorrate.

filter.add(key)

• key Buffer - key to add

Add a key to the set. Returnes true on success and false if the filter is full.

filter.has(key)

• key Buffer

Test if key is in the set

Class: ScalingBloem

new ScalingBloem(errorrate, options)

• errorrate Number

Creates an instance of a scaling bloom filter. Accepts a "options" Object that takes the following values:

• initialcapacity - the capacity of the first filter. Default: 1000
• scaling - the scaling factor. Use 2 here for less space usage but higher cpu usage or 4 for higher space, but lower cpu usage. Default: 2
• ratio - tightening ratio with 0 < ratio < 1. Default: 0.9

filter.add(key)

• key Buffer - key to add

Add a key to the set

filter.has(key)

• key Buffer

Test if key is in the set

References

• 1
• 2