bloem - npm Package Compare versions

Comparing version 0.1.0 to 0.2.0

bloem.js

@@ -58,4 +58,59 @@ "use strict";
 
+function SafeBloem(capacity, error_rate) {
+	var size   = calculateSize(capacity, error_rate)
+	var slices = calculateSlices(size, capacity)
+	this.capacity   = capacity
+	this.error_rate = error_rate
+	this.count  = 0
+	this.filter = new Bloem(size, slices)
+}
+
+SafeBloem.prototype = {
+	add: function(key) {
+		if(this.count >= this.capacity) {
+			return false
+		}
+		this.filter.add(key)
+		this.count++
+		return true
+	},
+	has: function(key) {
+		return this.filter.has(key)
+	}
+}
+
+function ScalingBloem(error_rate, options) {
+	var options = options || {}
+	this.error_rate       = error_rate
+	this.ratio            = options.ratio || 0.9
+	this.scaling          = options.scaling || 2
+	this.initial_capacity = options.initial_capacity|| 1000
+	this.filters = [new SafeBloem(this.initial_capacity, error_rate * (1 - this.ratio))]
+}
+
+ScalingBloem.prototype = {
+	add: function(key) {
+		var f = this.filters.slice(-1)[0]
+		if(f.add(key)) {
+			return
+		}
+		f = new SafeBloem(f.capacity * this.scaling, f.error_rate * this.ratio)
+		f.add(key)
+		this.filters.push(f)
+	},
+	has: function(key) {
+		for(var i = this.filters.length; i-- > 0; ) {
+			if(this.filters[i].has(key)) {
+				return true
+			}
+		}
+		return false
+	}
+}
+
+
 exports.Bloem = Bloem
+exports.SafeBloem = SafeBloem
+exports.ScalingBloem = ScalingBloem
 exports.calculateSize   = calculateSize
 exports.calculateSlices = calculateSlices

package.json

 {
 	"name":        "bloem",
-	"version":     "0.1.0",
+	"version":     "0.2.0",
 	"author":      "Sebastian Wiedenroth <[e-mail]>",
@@ -11,3 +11,9 @@ "description": "Bloom Filter using the FNV hash function",
 		"bitbuffer": "0.1.x"
+	},
+	"devDependencies": {
+		"mocha": "1.8.x"
+	},
+	"scripts": {
+		"test": "mocha -u qunit -R list"
 	}
 }

readme.md

 # Bloem - Bloom Filter for node.js
 
-Bloem implements a Bloom Filter for node.js.
-It uses the FNV Hash function and the optimization described in [[1](#lesshash)] by Kirsch and Mitzenmacher.
+Bloem implements three Bloom Filters for node.js.
+All use the FNV Hash function and the optimization described in [[1](#lesshash)] 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](#scale)]
 
@@ -13,4 +16,6 @@ ## Install
 
-	var Bloem = require('bloem')
-	var filter = new Bloem.Bloem(16, 2)
+#### Bloem
+
+	var bloem = require('bloem')
+	var filter = new bloem.Bloem(16, 2)
 	filter.has(Buffer("foobar")) // false
@@ -21,5 +26,17 @@ filter.add(Buffer("foobar"))
 
+##### 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
+
 ## References
 
-<a name="lesshash">
-[1] <http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.2442&rep=rep1&type=pdf>
+
+- <a name="lesshash"> [1] <http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.2442&rep=rep1&type=pdf>
+- <a name="scale"> [2] <http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.62.7953&rep=rep1&type=pdf>

No alert changes

Improved metrics

Total package byte prevSize

5908

increased by150.66%

Number of package files

4

increased by33.33%

Lines of code

158

increased by203.85%

Number of lines in readme file

40

increased by73.91%

Worsened metrics

Dev dependency count

1

increased byInfinity%

No dependency changes