Bloom Filter for node.js using the FNV hash function
JavaScript
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
.gitignore
LICENSE
bloem.js
package.json
readme.md
test.js

readme.md

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 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, error_rate)
  • capacity Number - capacity of the filter
  • error_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: 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