murmur-bloomfilter

murmur-bloomfilter

It's a Bloom filter, implemented using murmur hash function.

A bloom filter has two methods: add() and test(). You add() an element and voodoo happens; you test() for an element and it returns false if the element is definitely not in the set, or true if the element is probably in the set.

Installation

npm install murmur-bloomfilter --save

Usage:

var  BloomFilter = require("murmur-bloomfilter");

//Simple Usage: create a filter with  1000 expected item and 0.01 false positive probability.
/*
ie: if you are expecting to load 1000 items and you want to maintain a probability of not more than 0.01 false positives
*/
//Recomendded: it will calculate the best setup for your need.
var filter = new BloomFilter(1000, 0.01);

// Add some keys
filter.add("test")
filter.add("hey");

// Test them
console.log(filter.test("test")); // true
console.log(filter.test("man")); // false
console.log("false positive probability",filter.currentFPP())
console.log(filter.test("hey")); //true

/// advanced mode : use your own parameters for filter size and hash count (m,k)
var filter = new BloomFilter({m:1024,k:2});
filter.add("hey");
console.log(filter.test("hey")); // true

/// serialization interface:
var filter = new BloomFilter(1000, 0.01);
filter.add("hey");
filter.add("woot");
let buffer=filter.serialize();
var newFilter=new BloomFilter(buffer);
console.log(filter.test("hey")); // true


/// serialization interface:
var filter = new BloomFilter(1000, 0.01);
filter.add("hey");
filter.add("woot");
let buffer=filter.serialize();
var newFilter=new BloomFilter(buffer);
filter.test('woot'); // true

Implementation

Ported from geeksforgeeks.org tutourial.

• the hashing part is native.
• The hashing function is murmur, because it's fast and well-tested.
• Buffer is always in its serialized form, makes serializing fast.