Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

bloom-filters

Package Overview
Dependencies
Maintainers
2
Versions
28
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

bloom-filters - npm Package Compare versions

Comparing version 0.8.1 to 1.0.0

src/api.ts
src/base-filter.ts
src/bloom/bloom-filter.ts
src/bloom/counting-bloom-filter.ts
src/bloom/partitioned-bloom-filter.ts
src/cuckoo/bucket.ts
src/cuckoo/cuckoo-filter.ts
src/exportable.ts
src/formulas.ts
src/iblt/cell.ts
src/iblt/invertible-bloom-lookup-tables.ts
src/interfaces/classic-filter.ts
src/interfaces/counting-filter.ts
src/interfaces/writable-filter.ts
src/sketch/count-min-sketch.ts
src/utils.ts
tsconfig.json

26

package.json
{
"name": "bloom-filters",
"version": "0.8.1",
"version": "1.0.0",
"description": "JS implementation of probabilistic data structures: Bloom Filter (and its derived), HyperLogLog, Count-Min Sketch, Top-K and MinHash",
"main": "bloom-filters.js",
"scripts": {
"lint": "standard",
"build": "tsc",
"pretest": "yarn build",
"test": "mocha test/**/*-test.js --trace-deprecation --timeout=30000",
"coverage": "nyc --reporter=lcov npm test",
"report": "nyc npm test && nyc report --reporter=text-lcov > coverage.lcov",
"doc": "jsdoc -c jsdoc.json README.md src/",
"all": "npm run lint && npm run doc && npm run report"
"doc": "typedoc --mode file --out docs/ --ignoreCompilerErrors"
},

@@ -38,9 +36,12 @@ "repository": {

"devDependencies": {
"@types/lodash.eq": "^4.0.6",
"@types/lodash.indexof": "^4.0.6",
"@types/node": "^13.7.0",
"@types/seedrandom": "^2.4.28",
"@types/xxhashjs": "^0.2.1",
"chai": "^4.2.0",
"codecov": "^3.6.1",
"jsdoc": "^3.6.3",
"mocha": "^6.2.2",
"nyc": "^14.1.1",
"random": "^2.1.1",
"standard": "^14.3.1"
"typedoc": "^0.15.0",
"typescript": "^3.7.5"
},

@@ -51,4 +52,5 @@ "dependencies": {

"lodash.indexof": "^4.0.5",
"xxhashjs": "^0.2.2",
"seedrandom": "^3.0.5"
"reflect-metadata": "^0.1.13",
"seedrandom": "^3.0.5",
"xxhashjs": "^0.2.2"
},

@@ -55,0 +57,0 @@ "standard": {

222

README.md
# Bloom-Filters
[![Build Status](https://travis-ci.org/Callidon/bloom-filters.svg?branch=master)](https://travis-ci.org/Callidon/bloom-filters) [![codecov](https://codecov.io/gh/Callidon/bloom-filters/branch/master/graph/badge.svg)](https://codecov.io/gh/Callidon/bloom-filters)
[![Build Status](https://travis-ci.com/Callidon/bloom-filters.svg?branch=master)](https://travis-ci.com/Callidon/bloom-filters)

@@ -23,3 +23,3 @@ **Keywords:** bloom, filter, bloom filter, probabilistic, datastructure

* [Count Min Sketch](#count-min-sketch)
* [Invertible Bloom Filters (Key)](#invertible-bloom-filters)
* [Invertible Bloom Filters](#invertible-bloom-filters)
* [Export and import](#export-and-import)

@@ -35,3 +35,3 @@ * [Documentation](#documentation)

```bash
npm install bloom-filters --save
npm install bloom-filters --save
```

@@ -49,18 +49,34 @@

**Methods**:
* `add(element: string) -> void`: add an element into the filter.
* `has(element: string) -> boolean'`: Test an element for membership, returning False if the element is definitively not in the filter and True is the element might be in the filter.
* `equals(other: BloomFilter) -> boolean`: Test if two filters are equals.
* `rate() -> number`: compute the filter's false positive rate (or error rate).
```javascript
const { BloomFilter } = require('bloom-filters')
// create a Bloom Filter with size = 10 and 4% error rate
// create a Bloom Filter with a size of 10 and 4 hash functions
let filter = new BloomFilter(10, 4)
// insert data
filter.add('alice')
filter.add('bob')
// lookup for some data
console.log(filter.has('bob')) // output: true
console.log(filter.has('daniel')) // output: false
// print the error rate
console.log(filter.rate())
// alternatively, create a bloom filter optimal for a number of items and a desired error rate
const items = ['alice', 'bob']
const errorRate = 0.04 // 4 % error rate
filter = BloomFilter.create(items.length, errorRate)
// or create a bloom filter optimal for a collections of items and a desired error rate
filter = BloomFilter.from(items, errorRate)
```
Similar constructors:
- `BloomFilter.create(max_size, error_rate)`: create an optimal Bloom filter for a maximum of max_size elements with the desired error rate.
- `BloomFilter.from(array, error_rate)`: same as before, but create an optimal Bloom Filter for the size fo the array provided.
### Partitioned Bloom Filter

@@ -79,9 +95,14 @@

Otherwise, a Partitioned Bloom Filter **follows the same API than a [Classic Bloom Filter](#classic-bloom-filter)**.
**Methods**:
* `add(element: string) -> void`: add an element into the filter.
* `has(element: string) -> boolean'`: Test an element for membership, returning False if the element is definitively not in the filter and True is the element might be in the filter.
* `equals(other: PartitionedBloomFilter) -> boolean`: Test if two filters are equals.
* `rate() -> number`: compute the filter's false positive rate (or error rate).
```javascript
const { PartitionedBloomFilter } = require('bloom-filters')
// create a PartitionedBloomFilter of size 10 with 5 hash functions
const filter = new PartitionedBloomFilter(10, 5)
// create a PartitionedBloomFilter of size 10, with 5 hash functions and a load factor of 0.5
const filter = new PartitionedBloomFilter(10, 5, 0.5)

@@ -98,8 +119,12 @@ // add some value in the filter

// ...
// alternatively, create a PartitionedBloomFilter optimal for a number of items and a desired error rate
const items = ['alice', 'bob']
const errorRate = 0.04 // 4 % error rate
filter = PartitionedBloomFilter.create(items.length, errorRate)
// or create a PartitionedBloomFilter optimal for a collections of items and a desired error rate
filter = PartitionedBloomFilter.from(items, errorRate)
```
Similar constructors:
- `PartitionedBloomFilter.create(max_size, error_rate, load_factor)`: create an optimal Partitioned BloomFilter for a maximum of max_size elements with the desired error rate.
- `PartitionedBloomFilter.from(array, error_rate)`: same as before, but create an optimal Partitioned BloomFilter for the size fo the array provided.
### Cuckoo Filter

@@ -112,2 +137,10 @@

**Methods**:
* `add(element: string) -> void`: add an element into the filter.
* `remove(element: string) -> boolean`: delete an element from the filter, returning True if the deletion was a success and False otherwise.
* `has(element: string) -> boolean'`: Test an element for membership, returning False if the element is definitively not in the filter and True is the element might be in the filter.
* `equals(other: CuckooFilter) -> boolean`: Test if two filters are equals.
* `rate() -> number`: compute the filter's false positive rate (or error rate).
```javascript

@@ -128,9 +161,14 @@ const { CuckooFilter } = require('bloom-filters')

console.log(filter.has('bob')) // output: false
// alternatively, create a Cuckoo Filter optimal for a number of items and a desired error rate
const items = ['alice', 'bob']
const errorRate = 0.04 // 4 % error rate
filter = CuckooFilter.create(items.length, errorRate)
// or create a Cuckoo Filter optimal for a collections of items and a desired error rate
filter = CuckooFilter.from(items, errorRate)
```
Similar constructors:
- `CuckooFilter.create(max_size, error_rate, bucketSize, maxKicks, seed)`: Create an optimal Cuckoo Filter given the max number of elements, the error rate and the number of buckets.
**WARNING**: The error rate cannot be higher than `1 * 10^-18`. After this, You will get an error saying that the fingerprint length is higher than the hash length.
**Important**: The error rate can go up to 1.10^-18 = (0.000000000000000001). After this, You will get an error saying that the fingerprint length is higher than the hash length.
### Counting Bloom Filter

@@ -140,12 +178,18 @@

**Reference:** F. Bonomi, M. Mitzenmacher, R. Panigrahy, S. Singh, and G. Varghese, “An Improved Construction for Counting Bloom Filters,” in 14th Annual European Symposium on Algorithms, LNCS 4168, 2006, pp.
**Reference:** F. Bonomi, M. Mitzenmacher, R. Panigrahy, S. Singh, and G. Varghese, “An Improved Construction for Counting Bloom Filters,” in 14th Annual European Symposium on Algorithms, LNCS 4168, 2006
**Methods**:
* `add(element: string) -> void`: add an element into the filter.
* `remove(element: string) -> boolean`: delete an element from the filter, returning True if the deletion was a success and False otherwise.
* `has(element: string) -> boolean'`: Test an element for membership, returning False if the element is definitively not in the filter and True is the element might be in the filter.
* `equals(other: CountingBloomFilter) -> boolean`: Test if two filters are equals.
* `rate() -> number`: compute the filter's false positive rate (or error rate).
```javascript
const CountingBloomFilter = require('bloom-filters').CountingBloomFilter;
// create a Bloom Filter with capacity = 15 and 0.1% error rate
let filter = new CountingBloomFilter(15, 0.1);
// create a Bloom Filter with capacity = 15 and 4 hash functions
let filter = new CountingBloomFilter(15, 4);
// alternatively, create a Counting Bloom Filter from an array with 1% error rate
filter = CountingBloomFilter.from([ 'alice', 'bob' ], 0.1);
// add some value in the filter

@@ -166,8 +210,12 @@ filter.add('alice');

console.log(filter.rate());
// alternatively, create a Counting Bloom Filter optimal for a number of items and a desired error rate
const items = ['alice', 'bob']
const errorRate = 0.04 // 4 % error rate
filter = CountingBloomFilter.create(items.length, errorRate)
// or create a Counting Bloom Filter optimal for a collections of items and a desired error rate
filter = CountingBloomFilter.from(items, errorRate)
```
Similar constructors:
- `CountingBloomFilter.create(max_size, error_rate, load_factor)`: create an optimal Counting Bloom Filter for a maximum of max_size elements with the desired error rate.
- `CountingBloomFilter.from(array, error_rate)`: same as before, but create an optimal Counting Bloom Filter for the size fo the array provided.
### Count Min Sketch

@@ -181,9 +229,16 @@

**Methods**:
* `update(element: string, count = 1) -> void`: add `count` occurences of an element into the sketch.
* `count(element: string) -> number`: estimate the number of occurences of an element.
* `merge(other: CountMinSketch) -> CountMinSketch`: merge with occurences of two sketches.
* `equals(other: CountMinSketch) -> boolean`: Test if two sketchs are equals.
* `clone(): CountMinSketch`: Clone the sketch.
```javascript
const { CountMinSketch } = require('bloom-filters')
// create a new count min sketch with 2048 columns and 1 row
// create a new Count Min sketch with 2048 columns and 1 row
const sketch = new CountMinSketch(2048, 1)
// or create an optimal Count-Min-sketch with epsilon = 0.001 and delta = 0.001
// or sketck = CountMinSketch.create(0.001, 0.001)
// push some occurrences in the sketch

@@ -198,11 +253,17 @@ sketch.update('alice')

console.log(sketch.count('daniel')) // output: 0
```
Similar constructors:
- `CountMinSketch.create(epsilon, delta)`: create an optimal Count-min sketch for an epsilon and delta provided
// alternatively, create a Count Min sketch optimal for a target error rate and probability of accuracy
const items = ['alice', 'bob']
const errorRate = 0.04 // 4 % error rate
const accuracy = 0.99 // 99% accuracy
sketch = CountMinSketch.create(errorRate, accuracy)
// or create a Count Min Sketch optimal for a collections of items,
// a target error rate and probability of accuracy
sketch = CountMinSketch.from(items, errorRate, accuracy)
```
### Invertible Bloom Filters
An Invertible Bloom Lookup Table is a space-efficient and probabilistic data-structure for solving the set-difference problem efficiently without the use of logs or other prior context. It computes the set difference with communication proportional to the size of the difference between the sets being compared.
An Invertible Bloom Filters (IBLT), also called Invertible Bloom Lookup Table, is a space-efficient and probabilistic data-structure for solving the set-difference problem efficiently without the use of logs or other prior context. It computes the set difference with communication proportional to the size of the difference between the sets being compared.
They can simultaneously calculate D(A−B) and D(B−A) using O(d) space. This data structure encodes sets in a fashion that is similar in spirit to Tornado codes’ construction, in that it randomly combines elements using the XOR function.

@@ -212,65 +273,55 @@

**Inputs:** Only Accept Buffer (node: `require('buffer')` or browser `require('buffer/').Buffer`) as input
**WARNING**: An IBLT only accepts [`Buffer`](https://nodejs.org/api/buffer.html) as inputs. If you are using `bloom-filters` in a Web browser, you might consider using the [`feros/buffer`](https://www.npmjs.com/package/buffer) package, which provides a polyfill for `Buffer` in a browser.
**Methods:**
Please respects the method inputs and don't pass JSON exported structures as inputs. Import them before.
**Methods**
* `add(element: Buffer) -> void`: add an element into the filter.
* `remove(element: Buffer) -> void`: delete an element from the filter, returning True if the deletion was a success and False otherwise.
* `has(element: Buffer) -> boolean'`: Test an element for membership, returning False if the element is definitively not in the filter and True is the element might be in the filter.
* `equals(other: InvertibleBloomFilter) -> boolean`: Test if two filters are equals.
* `substract(remote: InvertibleBloomFilter)`: peform the XOR substraction of two IBLTs.
* `decode() -> {additional: Buffer[], missing: Buffer[]} `: decode an IBLT.
* `listEntries() -> Generator<Buffer, number, void>`: list all entries in the IBLT using a Generator.
* `add(element: Buffer) -> void`: add an element into the IBLT
* `delete(element: Buffer) -> void`: delete an element from the IBLT
* `has(element: Buffer) -> true|false|'perhaps'`: return whether an element is in the IBLT or not, or perhaphs in
* `substract(remote: InvertibleBloomFilter)`: this IBLT subtracted from remote, return another IBLT
* `static InvertibleBloomFilter.decode(subtracted: InvertibleBloomFilter) -> {additional: Buffer[], missing: Buffer[]} `: decode a subtracted IBLT
* `listEntries() -> {success: true|false, output: Buffer[]}`: list all entries in the IBLT
* getters:
* `length`: return the number of elements inserted, iterate on all count variables of all cells and return the average (sum/size)
* `size`: return the number of cells
* `hashCount`: return the number of times an element is hashed into the structure
* `elements`: return an array of all cells
```javascript
const { InvertibleBloomFilter } = require('bloom-filters')
// If you are a NODEJS user, no need to import Buffer
// otherwie, if you are a BROWSER-BASED user, you must import the buffer package (https://www.npmjs.com/package/buffer)
const hashcount = 3
const size = 50
const iblt = new InvertibleBloomFilter(size, hashcount)
const remote = new InvertibleBloomFilter(size, hashcount)
// push some data in the iblt
const data = [Buffer.from('alice'),
Buffer.from(JSON.stringify(42)),
Buffer.from('help'),
Buffer.from('meow'),
Buffer.from('json')]
// push some data in the IBLT
iblt.add(Buffer.from('alice'))
iblt.add(Buffer.from('42'))
iblt.add(Buffer.from('help'))
iblt.add(Buffer.from('meow'))
iblt.add(Buffer.from('json'))
data.forEach(e => iblt.add(e))
console.log(ilbt.has(Buffer.from('alice'))) // output: true
console.log(ilbt.has(Buffer.from('daniel'))) // output: false
const remoteData = [Buffer.from('alice'),
Buffer.from('car'),
Buffer.from('meow'),
Buffer.from('help')]
iblt.remove(Buffer.from('alice'))
console.log(ilbt.has(Buffer.from('alice'))) // output: false
remoteData.forEach(e => remote.add(e))
// Now, let's demonstrate the decoding power of IBLT!
const remote = new InvertibleBloomFilter(size, hashcount)
remote.add(Buffer.from('alice'))
remote.add(Buffer.from('car'))
remote.add(Buffer.from('meow'))
remote.add(Buffer.from('help'))
const sub = iblt.substract(remote)
const result = InvertibleBloomFilter.decode(sub)
console.log('Did we successfully decode the subtracted iblts?', result.success, result.reason)
console.log('Missing elements for iblt: ', result.missing, result.missing.map(e => e.toString()))
console.log('Additional elements of iblt and missing elements of the remote iblt: ', result.additional, result.additional.map(e => e.toString()))
// create the iblt like before
console.log('Verify if Buffer.from("help") is in the iblt: ', iblt.has(Buffer.from('help')))
// true with high probability if well configured
// decode the difference between the two filters
const result = iblt.substract(remote).decode()
iblt.delete(Buffer.from('help'))
// no error ;)
console.log(`Did we successfully decode the subtracted iblts? ${result.success}. Why? $${result.reason}`)
console.log(`Elements of iblt missing elements from remote: ${result.additional}`)
console.log(`Elements of remote missing elements from iblt: ${result.missing}`)
console.log('Deleting Buffer.from("help") and rechecking:', iblt.has(Buffer.from('help')))
// alternatively, create an IBLT optimal for a number of items and a desired error rate
const items = [Buffer.from('alice'), Buffer.from('bob')]
const errorRate = 0.04 // 4 % error rate
filter = InvertibleBloomFilter.create(items.length, errorRate)
const list = iblt.listEntries()
console.log('Remaining entries after deletion: ', list.success, list.output.map(e => e.toString()))
// or create an IBLT optimal for a collections of items and a desired error rate
filter = InvertibleBloomFilter.from(items, errorRate)
```
The example can be run in tests/iblt-example.js

@@ -309,4 +360,4 @@ **Tuning the IBLT** We recommend to use at least a **hashcount** of 3 and an **alpha** of 1.5 for at least 50 differences, which equals to 1.5*50 = 75 cells. Then, if you insert a huge number of values in there, the decoding will work (whatever the number of differences less than 50) but testing the presence of a value is still probabilistic, based on the number of elements inserted (Even for the functions like listEntries). For more details, you should read the seminal research paper on IBLTs ([full-text article](http://www.sysnet.ucsd.edu/sysnet/miscpapers/EppGooUye-SIGCOMM-11.pdf)).

```javascript
const BloomFilter = require('bloom-filter')
const bl = new BloomFilter.MyBloomFilter(...)
const { BloomFilter } = require('bloom-filter')
const bl = new BloomFilter(...)
console.log(bl.seed) // 78187493520

@@ -327,5 +378,2 @@ bl.seed = 0xABCD

npm test
# generate coverage with istanbul
npm run coverage
```

@@ -344,2 +392,4 @@

**v1.0.0**: Rework the whole library using TypeScript, unify the API and fix the documentation.
**v0.8.0**: Fix some issues with the cuckoo filter (performances). Fix the global API. It allows now to customize each Filter. If you want to use the old API, use the `.create()` or `.from()` functions to match the old api.

@@ -346,0 +396,0 @@

47

test/bloom-filter-test.js

@@ -28,3 +28,3 @@ /* file : bloom-filter-test.js

require('chai').should()
const BloomFilter = require('../src/bloom-filter.js')
const { BloomFilter } = require('../dist/api.js')

@@ -48,3 +48,3 @@ describe('BloomFilter', () => {

const expectedHashes = Math.ceil((expectedSize / data.length) * Math.log(2))
const filter = BloomFilter.from(data, targetRate, seed)
const filter = BloomFilter.from(data, targetRate)
filter.size.should.equal(expectedSize)

@@ -58,3 +58,3 @@ filter._nbHashes.should.equal(expectedHashes)

describe('#has', () => {
const filter = BloomFilter.from(['alice', 'bob', 'carl'], targetRate, seed)
const filter = BloomFilter.from(['alice', 'bob', 'carl'], targetRate)
it('should return false for elements that are definitively not in the set', () => {

@@ -72,2 +72,28 @@ filter.has('daniel').should.equal(false)

describe('#equals', () => {
it('should returns True when two filters are equals', () => {
const first = BloomFilter.from(['alice', 'bob', 'carol'], targetRate)
const other = BloomFilter.from(['alice', 'bob', 'carol'], targetRate)
first.equals(other).should.equal(true)
})
it('should returns False when two filters have different sizes', () => {
const first = new BloomFilter(15, 4)
const other = new BloomFilter(10, 4)
first.equals(other).should.equal(false)
})
it('should returns False when two filters have different nb. of hash functions', () => {
const first = new BloomFilter(15, 4)
const other = new BloomFilter(15, 2)
first.equals(other).should.equal(false)
})
it('should returns False when two filters have different content', () => {
const first = BloomFilter.from(['alice', 'bob', 'carol'], targetRate)
const other = BloomFilter.from(['alice', 'bob', 'daniel'], targetRate)
first.equals(other).should.equal(false)
})
})
describe('#saveAsJSON', () => {

@@ -92,3 +118,3 @@ const filter = BloomFilter.from(['alice', 'bob', 'carl'], targetRate, seed)

const newFilter = BloomFilter.fromJSON(exported)
newFilter.seed.should.equal(seed)
newFilter.seed.should.equal(filter.seed)
newFilter.size.should.equal(filter._size)

@@ -104,10 +130,10 @@ newFilter.length.should.equal(filter._length)

{ type: 'BloomFilter' },
{ type: 'BloomFilter', size: 1 },
{ type: 'BloomFilter', size: 1, length: 1 },
{ type: 'BloomFilter', size: 1, length: 1, nbHashes: 2 },
{ type: 'BloomFilter', size: 1, length: 1, nbHashes: 2, seed: 1 }
{ type: 'BloomFilter', _size: 1 },
{ type: 'BloomFilter', _size: 1, _length: 1 },
{ type: 'BloomFilter', _size: 1, _length: 1, _nbHashes: 2 },
{ type: 'BloomFilter', _size: 1, _length: 1, _nbHashes: 2, seed: 1 }
]
invalids.forEach(json => {
(() => BloomFilter.fromJSON(json)).should.throw(Error, 'Cannot create a BloomFilter from a JSON export which does not represent a bloom filter')
(() => BloomFilter.fromJSON(json)).should.throw(Error)
})

@@ -120,3 +146,3 @@ })

const targetedRate = 0.01
it('should not return an error when inserting ' + max + ' elements', () => {
it(`should not return an error when inserting ${max} elements`, () => {
const filter = BloomFilter.create(max, targetedRate)

@@ -137,3 +163,2 @@ for (let i = 0; i < max; ++i) filter.add('' + i)

const currentrate = falsePositive / tries
console.log('BloomFilter false positive rate on %d tests: ', tries, currentrate)
currentrate.should.be.closeTo(targetedRate, targetedRate)

@@ -140,0 +165,0 @@ })

2

test/bucket-test.js

@@ -28,3 +28,3 @@ /* file : bucket-test.js

require('chai').should()
const Bucket = require('../src/bucket.js')
const Bucket = require('../dist/cuckoo/bucket.js').default

@@ -31,0 +31,0 @@ describe('Bucket', () => {

27

test/count-min-sketch-test.js

@@ -28,3 +28,3 @@ /* file : count-min-sketch-test.js

require('chai').should()
const CountMinSketch = require('../src/count-min-sketch.js')
const { CountMinSketch } = require('../dist/api.js')

@@ -108,3 +108,3 @@ describe('CountMinSketch', () => {

exported._columns.should.equal(sketch._columns)
exported._N.should.be.equal(sketch._N)
exported._allSums.should.be.equal(sketch._allSums)
exported._matrix.should.deep.equal(sketch._matrix)

@@ -116,5 +116,5 @@ })

const newSketch = CountMinSketch.fromJSON(exported)
newSketch.w.should.equal(sketch.w)
newSketch.d.should.equal(sketch.d)
newSketch.N.should.be.equal(sketch.N)
newSketch.columns.should.equal(sketch.columns)
newSketch.rows.should.equal(sketch.rows)
newSketch.sum.should.be.equal(sketch.sum)
newSketch._matrix.should.deep.equal(sketch._matrix)

@@ -127,13 +127,13 @@ })

{ type: 'CountMinSketch' },
{ type: 'CountMinSketch', w: 1 },
{ type: 'CountMinSketch', w: 1, d: 1 },
{ type: 'CountMinSketch', w: 1, d: 1, seed: 1 }
{ type: 'CountMinSketch', _columns: 1 },
{ type: 'CountMinSketch', _columns: 1, _rows: 1 },
{ type: 'CountMinSketch', _columns: 1, _rows: 1, seed: 1 }
]
invalids.forEach(json => {
(() => CountMinSketch.fromJSON(json)).should.throw(Error, 'Cannot create a CountMinSketch from a JSON export which does not represent a count-min sketch')
(() => CountMinSketch.fromJSON(json)).should.throw(Error)
})
})
})
describe('Performance test', () => {
describe.skip('Performance test', () => {
// setup an finite stream of 100 000 elements between [0; 1000)

@@ -148,3 +148,2 @@ const max = 1000000

const filter = CountMinSketch.create(rate, delta)
filter.seed = 1
// error rate 0.001, probability of wrong answer: 0.001

@@ -171,3 +170,3 @@ // console.log('number of rows:', filter._rows)

const count = filter.count('' + item)
const est = map.get(item) + rate * filter.N
const est = map.get(item) + rate * filter.sum
if (count > est) {

@@ -180,5 +179,3 @@ error += 1

const errorRate = error / max
const errorProb = 1 - Math.pow(Math.E, -filter.d)
console.log('Number of errors: %d/%d with prob = %d', error, max, errorProb)
console.log('Rate: ', errorRate)
const errorProb = 1 - Math.pow(Math.E, -filter.rows)
errorRate.should.be.at.most(errorProb)

@@ -185,0 +182,0 @@ })

55

test/counting-bloom-filter-test.js

@@ -28,7 +28,6 @@ /* file : counting-bloom-filter-test.js

require('chai').should()
const CountingBloomFilter = require('../src/counting-bloom-filter.js')
const { CountingBloomFilter } = require('../dist/api.js')
describe('CountingBloomFilter', () => {
const targetRate = 0.1
const seed = Math.random()

@@ -38,3 +37,2 @@ describe('construction', () => {

const filter = CountingBloomFilter.create(15, targetRate)
filter.seed = seed
filter.add('alice')

@@ -49,3 +47,3 @@ filter.add('bob')

const expectedHashes = Math.ceil((expectedSize / data.length) * Math.log(2))
const filter = CountingBloomFilter.from(data, targetRate, seed)
const filter = CountingBloomFilter.from(data, targetRate)
filter.size.should.equal(expectedSize)

@@ -59,3 +57,3 @@ filter._nbHashes.should.equal(expectedHashes)

describe('#has', () => {
const filter = CountingBloomFilter.from(['alice', 'bob', 'carl'], targetRate, seed)
const filter = CountingBloomFilter.from(['alice', 'bob', 'carl'], targetRate)
it('should return false for elements that are definitively not in the set', () => {

@@ -73,6 +71,6 @@ filter.has('daniel').should.equal(false)

describe('#delete', () => {
describe('#remove', () => {
it('should allow deletion of items', () => {
const filter = CountingBloomFilter.from(['alice', 'bob', 'carl'], targetRate, seed)
filter.delete('bob')
const filter = CountingBloomFilter.from(['alice', 'bob', 'carl'], targetRate)
filter.remove('bob')
filter.has('alice').should.equal(true)

@@ -84,4 +82,30 @@ filter.has('bob').should.equal(false)

describe('#equals', () => {
it('should returns True when two filters are equals', () => {
const first = CountingBloomFilter.from(['alice', 'bob', 'carol'], targetRate)
const other = CountingBloomFilter.from(['alice', 'bob', 'carol'], targetRate)
first.equals(other).should.equal(true)
})
it('should returns False when two filters have different sizes', () => {
const first = new CountingBloomFilter(15, 4)
const other = new CountingBloomFilter(10, 4)
first.equals(other).should.equal(false)
})
it('should returns False when two filters have different nb. of hash functions', () => {
const first = new CountingBloomFilter(15, 4)
const other = new CountingBloomFilter(15, 2)
first.equals(other).should.equal(false)
})
it('should returns False when two filters have different content', () => {
const first = CountingBloomFilter.from(['alice', 'bob', 'carol'], targetRate)
const other = CountingBloomFilter.from(['alice', 'bob', 'daniel'], targetRate)
first.equals(other).should.equal(false)
})
})
describe('#saveAsJSON', () => {
const filter = CountingBloomFilter.from(['alice', 'bob', 'carl'], targetRate, seed)
const filter = CountingBloomFilter.from(['alice', 'bob', 'carl'], targetRate)
it('should export a bloom filter to a JSON object', () => {

@@ -100,3 +124,3 @@ const exported = filter.saveAsJSON()

const newFilter = CountingBloomFilter.fromJSON(exported)
newFilter.seed.should.equal(seed)
newFilter.seed.should.equal(filter.seed)
newFilter.size.should.equal(filter._size)

@@ -112,10 +136,10 @@ newFilter.length.should.equal(filter._length)

{ type: 'CountingBloomFilter' },
{ type: 'CountingBloomFilter', size: 1 },
{ type: 'CountingBloomFilter', size: 1, length: 1 },
{ type: 'CountingBloomFilter', size: 1, length: 1, nbHashes: 2 },
{ type: 'CountingBloomFilter', size: 1, length: 1, nbHashes: 2, seed: 1 }
{ type: 'CountingBloomFilter', _size: 1 },
{ type: 'CountingBloomFilter', _size: 1, _length: 1 },
{ type: 'CountingBloomFilter', size: 1, length: 1, _nbHashes: 2 },
{ type: 'CountingBloomFilter', _size: 1, _length: 1, _nbHashes: 2, _seed: 1 }
]
invalids.forEach(json => {
(() => CountingBloomFilter.fromJSON(json)).should.throw(Error, 'Cannot create a CountingBloomFilter from a JSON export which does not represent a bloom filter')
(() => CountingBloomFilter.fromJSON(json)).should.throw(Error)
})

@@ -144,3 +168,2 @@ })

const currentrate = falsePositive / tries
console.log('CountingBloomFilter false positive rate on %d tests: ', tries, currentrate)
currentrate.should.be.closeTo(targetedRate, targetedRate)

@@ -147,0 +170,0 @@ })

43

test/cuckoo-filter-test.js

@@ -30,5 +30,4 @@ /* file : cuckoo-filter-test.js

chai.expect()
const CuckooFilter = require('../src/cuckoo-filter.js')
const utils = require('../src/utils')
const seed = 1
const { CuckooFilter } = require('../dist/api.js')
const utils = require('../dist/utils')

@@ -39,5 +38,4 @@ describe('CuckooFilter', () => {

const filter = new CuckooFilter(15, 3, 2, 1)
filter.seed = (seed)
const element = 'foo'
const hashes = utils.hashIntAndString(element, seed, 16, 64)
const hashes = utils.hashIntAndString(element, filter.seed, 16, 64)
const hash = hashes.int

@@ -47,3 +45,3 @@ const fingerprint = hashes.string.substring(0, 3)

const firstIndex = Math.abs(hash)
const secondIndex = Math.abs(firstIndex ^ Math.abs(utils.hashAsInt(fingerprint, seed, 64)))
const secondIndex = Math.abs(firstIndex ^ Math.abs(utils.hashAsInt(fingerprint, filter.seed, 64)))

@@ -60,3 +58,2 @@ const locations = filter._locations(element)

const filter = CuckooFilter.create(15, 0.01)
filter.seed = (seed)
let nbElements = 0

@@ -74,3 +71,2 @@ filter.add('alice')

const filter = CuckooFilter.create(15, 0.01, 2)
filter.seed = (seed)
const element = 'foo'

@@ -96,3 +92,2 @@ let nbElements = 0

const filter = new CuckooFilter(15, 3, 1, 1)
filter.seed = (seed)
const element = 'foo'

@@ -119,3 +114,2 @@ let nbElements = 0

const filter = new CuckooFilter(1, 3, 1)
filter.seed = (seed)
const element = 'foo'

@@ -128,3 +122,2 @@ filter.add(element)

const filter = new CuckooFilter(10, 3, 1)
filter.seed = (seed)
filter.add('a').should.equal(true)

@@ -149,3 +142,2 @@ filter.add('b').should.equal(true)

const filter = new CuckooFilter(10, 3, 1)
filter.seed = (seed)
filter.add('a').should.equal(true)

@@ -171,3 +163,2 @@ filter.add('b').should.equal(true)

const filter = new CuckooFilter(15, 3, 1)
filter.seed = (seed)
const element = 'foo'

@@ -183,3 +174,2 @@ const locations = filter._locations(element)

const filter = new CuckooFilter(15, 3, 1)
filter.seed = (seed)
const element = 'foo'

@@ -198,3 +188,2 @@ const locations = filter._locations(element)

const filter = new CuckooFilter(15, 3, 1)
filter.seed = (seed)
filter.add('foo')

@@ -208,3 +197,2 @@ filter.remove('moo').should.equal(false)

const filter = new CuckooFilter(15, 3, 1)
filter.seed = (seed)
filter.add('foo')

@@ -216,3 +204,2 @@ filter.has('foo').should.equal(true)

const filter = new CuckooFilter(15, 3, 1)
filter.seed = (seed)
filter.add('foo')

@@ -224,3 +211,2 @@ filter.has('moo').should.equal(false)

const filter = new CuckooFilter(15, 3, 1)
filter.seed = (seed)
filter.add('foo')

@@ -234,3 +220,2 @@ filter.add('foo')

const filter = CuckooFilter.create(15, 0.01)
filter.seed = (seed)
filter.add('alice')

@@ -247,16 +232,10 @@ filter.add('andrew')

const one = filter.has('samx') // output: false [ok]
// console.log(one)
one.should.equal(false)
const two = filter.has('samy') // output: true [?]
// console.log(two)
// filter._filter.forEach(b => console.log(b._elements))
two.should.equal(false)
const three = filter.has('alice') // output: true [ok]
// console.log(three)
three.should.equal(true)
const four = filter.has('joe') // output: true [?]
// console.log(four)
four.should.equal(false)
const five = filter.has('joe') // output: true [?]
// console.log(five)
five.should.equal(false)

@@ -268,3 +247,2 @@ })

const filter = new CuckooFilter(15, 3, 2)
filter.seed = (seed)
filter.add('alice')

@@ -297,7 +275,7 @@ filter.add('bob')

{ type: 'CuckooFilter' },
{ type: 'CuckooFilter', size: 1 },
{ type: 'CuckooFilter', size: 1, fingerprintLength: 1 },
{ type: 'CuckooFilter', size: 1, fingerprintLength: 1, length: 2 },
{ type: 'CuckooFilter', size: 1, fingerprintLength: 1, length: 2, maxKicks: 1 },
{ type: 'CuckooFilter', size: 1, fingerprintLength: 1, length: 2, maxKicks: 1, seed: 1 }
{ type: 'CuckooFilter', _size: 1 },
{ type: 'CuckooFilter', _size: 1, _fingerprintLength: 1 },
{ type: 'CuckooFilter', _size: 1, _fingerprintLength: 1, _length: 2 },
{ type: 'CuckooFilter', _size: 1, _fingerprintLength: 1, _length: 2, _maxKicks: 1 },
{ type: 'CuckooFilter', _size: 1, _fingerprintLength: 1, _length: 2, _maxKicks: 1, _seed: 1 }
]

@@ -315,3 +293,3 @@

it('should not return an error when inserting and asking for ' + max + ' elements, rate = ' + rate + ', bucketSize = ' + bucketSize, () => {
const filter = CuckooFilter.create(max, rate, bucketSize, 500, seed)
const filter = CuckooFilter.create(max, rate, bucketSize, 500)
for (let i = 0; i < max; i++) {

@@ -330,3 +308,2 @@ filter.add('' + i).should.equal(true)

const currentrate = falsePositive / tries
console.log('CuckooFilter false positive rate on %d tests: ', tries, currentrate, filter._computeHashTableLoad())
currentrate.should.be.closeTo(rate, rate)

@@ -333,0 +310,0 @@ })

2

test/iblt-example.js

@@ -1,2 +0,2 @@

const { InvertibleBloomFilter } = require('../bloom-filters')
const { InvertibleBloomFilter } = require('../dist/api.js')
// the buffer package is auto imported by nodejs

@@ -3,0 +3,0 @@ // create a new Invertible Bloom Filters with 1000 cells and 4 hash functions

84

test/iblt-test.js

@@ -29,3 +29,3 @@ /* file : bloom-filter-test.js

require('chai').expect()
const InvertibleBloomFilter = require('../src/invertible-bloom-lookup-tables.js').InvertibleBloomFilter
const { InvertibleBloomFilter } = require('../dist/api.js')
const random = require('random')

@@ -62,4 +62,4 @@ const seedrandom = require('seedrandom')

describe('#delete', () => {
it('should delete element from the iblt with #delete', () => {
describe('#remove', () => {
it('should remove element from the iblt', () => {
const iblt = new InvertibleBloomFilter(size, hashCount)

@@ -76,3 +76,3 @@ iblt.seed = seed

toInsert.forEach(e => {
iblt.delete(e)
iblt.remove(e)
})

@@ -86,11 +86,9 @@ iblt.length.should.equal(0)

const iblt = new InvertibleBloomFilter(size, hashCount)
iblt.seed = seed
iblt._hashCount.should.equal(hashCount)
iblt.size.should.equal(size)
iblt.length.should.equal(0)
iblt._elements.length.should.equal(size)
toInsert.forEach(e => {
iblt.add(e)
iblt.has(e).should.equal(true)
})
toInsert.forEach(e => {
const query = iblt.has(e)
query.should.equal(true)
})
})

@@ -100,15 +98,17 @@ })

describe('#listEntries', () => {
it('should get all element from the iblt with #listEntries', () => {
it('should get all element from the filter', () => {
const iblt = new InvertibleBloomFilter(size, hashCount)
iblt.seed = seed
iblt._hashCount.should.equal(hashCount)
iblt.size.should.equal(size)
iblt.length.should.equal(0)
iblt._elements.length.should.equal(size)
toInsert.forEach(e => {
iblt.add(e)
})
const res = iblt.listEntries()
res.success.should.equal(true)
res.output.sort().should.eql(toInsert.sort())
const iterator = iblt.listEntries()
const output = []
let elt = iterator.next()
while(!elt.done) {
output.push(elt.value)
elt = iterator.next()
}
elt.value.should.equal(true)
output.length.should.equals(toInsert.length)
output.sort().should.eqls(toInsert.sort())
})

@@ -119,9 +119,16 @@ })

it('should create correctly an IBLT', () => {
const iblt = InvertibleBloomFilter.create(size, 0.001, seed, true)
const iblt = InvertibleBloomFilter.create(size, 0.001)
toInsert.forEach(e => {
iblt.add(e)
})
const res = iblt.listEntries()
res.success.should.equal(true)
res.output.sort().should.eql(toInsert.sort())
const iterator = iblt.listEntries()
const output = []
let elt = iterator.next()
while(!elt.done) {
output.push(elt.value)
elt = iterator.next()
}
elt.value.should.equal(true)
output.length.should.equals(toInsert.length)
output.sort().should.eqls(toInsert.sort())
})

@@ -131,6 +138,6 @@ })

describe('#saveAsJSON', () => {
const iblt = InvertibleBloomFilter.from([Buffer.from('meow'), Buffer.from('car')], 100, 4, seed)
const iblt = InvertibleBloomFilter.from([Buffer.from('meow'), Buffer.from('car')], 0.001)
it('should export an Invertible Bloom Filter to a JSON object', () => {
const exported = iblt.saveAsJSON()
const exported = iblt.saveAsJSON()
exported._seed.should.equal(seed)

@@ -140,3 +147,3 @@ exported.type.should.equal('InvertibleBloomFilter')

exported._hashCount.should.equal(iblt.hashCount)
exported._elements.should.deep.equal(iblt._elements)
exported._elements.should.deep.equal(iblt._elements.map(e => e.saveAsJSON()))
})

@@ -147,6 +154,3 @@

const newIblt = InvertibleBloomFilter.fromJSON(exported)
newIblt.seed.should.equal(seed)
newIblt.size.should.equal(iblt._size)
newIblt.hashCount.should.equal(iblt._hashCount)
newIblt.elements.should.deep.equal(iblt._elements)
iblt.equals(newIblt).should.equals(true)
})

@@ -168,3 +172,3 @@

InvertibleBloomFilter.fromJSON(json)
}).should.throw(Error, 'Cannot create an InvertibleBloomFilter from a JSON export which does not represent an Invertible Bloom Filter')
}).should.throw(Error)
})

@@ -178,3 +182,3 @@ })

})
}).should.not.throw(Error, 'Cannot create an InvertibleBloomFilter from a JSON export which does not represent an Invertible Bloom Filter')
}).should.not.throw(Error)
})

@@ -200,7 +204,7 @@ })

function commonTest (size, hashCount, keys, prefix, differences) {
const iblt = new InvertibleBloomFilter(size, hashCount, seed, true)
const iblt = new InvertibleBloomFilter(size, hashCount, seed)
iblt.seed = seed
const setDiffplus = []
const setDiffminus = []
const remote = new InvertibleBloomFilter(size, hashCount, seed, true)
const remote = new InvertibleBloomFilter(size, hashCount, seed)
remote.seed = seed

@@ -226,11 +230,11 @@ for (let i = 1; i <= keys; ++i) {

const sub = iblt.substract(remote)
const res = InvertibleBloomFilter.decode(sub)
const res = sub.decode()
try {
res.success.should.equal(true)
} catch (e) {
console.log('Additional: ', res.additional, ' Missing: ', res.missing)
console.log('Additional: ', res.additional.map(e => e.toString()), ' Missing: ', res.missing.map(e => e.toString()))
console.log('Additional: ', res.additional.map(e => e.toString()).length, ' Missing: ', res.missing.map(e => e.toString()).length)
console.log('Number of differences found: ', res.additional.length + res.missing.length)
console.log('Should have: ', setDiffplus.length, setDiffminus.length, setDiffminus.length + setDiffplus.length)
// console.log('Additional: ', res.additional, ' Missing: ', res.missing)
// console.log('Additional: ', res.additional.map(e => e.toString()), ' Missing: ', res.missing.map(e => e.toString()))
// console.log('Additional: ', res.additional.map(e => e.toString()).length, ' Missing: ', res.missing.map(e => e.toString()).length)
// console.log('Number of differences found: ', res.additional.length + res.missing.length)
// console.log('Should have: ', setDiffplus.length, setDiffminus.length, setDiffminus.length + setDiffplus.length)
throw e

@@ -237,0 +241,0 @@ }

52

test/partitioned-bloom-filter-test.js

@@ -28,3 +28,3 @@ /* file : partitioned-bloom-filter-test.js

require('chai').should()
const PartitionedBloomFilter = require('../src/partitioned-bloom-filter.js')
const { PartitionedBloomFilter } = require('../dist/api.js')

@@ -35,3 +35,3 @@ describe('PartitionedBloomFilter', () => {

describe('construction', () => {
it('should add element to the filter with #add', () => {
it('should add element to the filter', () => {
const filter = PartitionedBloomFilter.create(15, targetRate)

@@ -45,7 +45,6 @@ filter.add('alice')

const data = ['alice', 'bob', 'carl']
const expectedSize = PartitionedBloomFilter._computeOptimalNumberOfCells(data.length, targetRate)
const expectedHashes = PartitionedBloomFilter._computeOptimalNumberOfhashes(targetRate)
const filter = PartitionedBloomFilter.from(data, targetRate)
filter.size.should.equal(expectedSize)
filter._nbHashes.should.equal(expectedHashes)
filter.has('alice').should.equal(true)
filter.has('bob').should.equal(true)
filter.has('carl').should.equal(true)
filter.length.should.equal(data.length)

@@ -74,2 +73,34 @@ filter.rate().should.be.closeTo(targetRate, 0.1)

describe('#equals', () => {
it('should returns True when two filters are equals', () => {
const first = PartitionedBloomFilter.from(['alice', 'bob', 'carol'], targetRate, 0.5)
const other = PartitionedBloomFilter.from(['alice', 'bob', 'carol'], targetRate, 0.5)
first.equals(other).should.equal(true)
})
it('should returns False when two filters have different sizes', () => {
const first = new PartitionedBloomFilter(15, 4, 0.5)
const other = new PartitionedBloomFilter(10, 4, 0.5)
first.equals(other).should.equal(false)
})
it('should returns False when two filters have different nb. of hash functions', () => {
const first = new PartitionedBloomFilter(15, 4, 0.5)
const other = new PartitionedBloomFilter(15, 2, 0.5)
first.equals(other).should.equal(false)
})
it('should returns False when two filters have different load factor', () => {
const first = new PartitionedBloomFilter(15, 4, 0.5)
const other = new PartitionedBloomFilter(15, 2, 0.4)
first.equals(other).should.equal(false)
})
it('should returns False when two filters have different content', () => {
const first = PartitionedBloomFilter.from(['alice', 'bob', 'carol'], targetRate, 0.5)
const other = PartitionedBloomFilter.from(['alice', 'bob', 'daniel'], targetRate, 0.5)
first.equals(other).should.equal(false)
})
})
describe('#saveAsJSON', () => {

@@ -107,8 +138,8 @@ const filter = PartitionedBloomFilter.create(15, targetRate)

{ type: 'PartitionedBloomFilter' },
{ type: 'PartitionedBloomFilter', capacity: 1 },
{ type: 'PartitionedBloomFilter', capacity: 1, errorRate: 1 }
{ type: 'PartitionedBloomFilter', _capacity: 1 },
{ type: 'PartitionedBloomFilter', _capacity: 1, _errorRate: 1 }
]
invalids.forEach(json => {
(() => PartitionedBloomFilter.fromJSON(json)).should.throw(Error, 'Cannot create a PartitionedBloomFilter from a JSON export which does not represent a Partitioned Bloom Filter')
(() => PartitionedBloomFilter.fromJSON(json)).should.throw(Error)
})

@@ -119,3 +150,3 @@ })

const max = 1000
it('should not return an error when inserting and querying for ' + max + ' elements', () => {
it(`should not return an error when inserting and querying for ${max} elements`, () => {
const filter = PartitionedBloomFilter.create(max, targetRate, 0.5)

@@ -136,3 +167,2 @@ for (let i = 0; i < max; ++i) filter.add('' + i)

const currentrate = falsePositive / tries
console.log('PartitionedBloomFilter false positive rate on %d tests = %d (targeted = %d)', tries, currentrate, targetRate)
currentrate.should.be.closeTo(targetRate, targetRate)

@@ -139,0 +169,0 @@ })

2

test/utils-test.js

@@ -28,3 +28,3 @@ /* file : utils-test.js

require('chai').should()
const utils = require('../src/utils.js')
const utils = require('../dist/utils.js')
const XXH = require('xxhashjs')

@@ -31,0 +31,0 @@ const seed = utils.getDefaultSeed()

bloom-filters.js
deploy_doc.sh
jsdoc.json
src/bloom-filter.js
src/bucket.js
src/count-min-sketch.js
src/counting-bloom-filter.js
src/cuckoo-filter.js
src/export-import-specs.js
src/exportable.js
src/formulas.js
src/invertible-bloom-lookup-tables.js
src/partitioned-bloom-filter.js
src/utils.js
.travis.yml

Sorry, the diff of this file is not supported yet

LICENSE

Sorry, the diff of this file is not supported yet

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc