Bloem - Bloom Filter for node.js
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 bitfieldslices
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, error_rate)
capacity
Number - capacity of the filtererror_rate
Number
Create a new bloom filter that can hold capacity
elements with an error probability of error_rate
.
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(error_rate, options)
error_rate
Number
Creates an instance of a scaling bloom filter. Accepts a "options" Object that takes the following values:
initial_capacity
- the capacity of the first filter. Default: 1000scaling
- the scaling factor. Use 2 here for less space usage but higher cpu usage or 4 for higher space, but lower cpu usage. Default: 2ratio
- 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