1.0.4 • Published 6 years ago
node_bloom_filter v1.0.4
Node Bloom filter
Node bloom filter is a sophisticated Bloom filter available for NodeJs which can be optionally transformed to a counting bloom filter and can thus perform delete operations as well.
- Supports deletions
- Can yield a desired false positive rate(probability) when given the total number of elements in the sets
- Supports an optimisation flag to calculate the number of hashes and bits to use internally
- Serialization to an Arraybuffer, which can be converted to JSON/UTF-8/base64 and is left to the user :)
- Dynamically resizes the underlying Arraybuffer to handle the counter overflows when used as a counting bloom filter.
- Implements double hashing technique to generate multiple hashes using murmur3
- Uses bit manipulations to optimise on memory usage
- When implemented as a counting bloom filter, it can support 4,8,16,32 bits per counters to handle overflows
- Extends Events to notify when the underlying Arraybuffer is resized
Getting Started
To install: npm install node_bloom_filter
Usage
Bloom Filter
To create a general implementation, pass the following in the constructor:
let bFilter = new bloomFilter({
nHash:10,
nBits:1024*8
});
If no options are passed, the filter created by default can support 569 members with a false rate of upto 0.001
To create the optimized implementation, pass an object in the constructor:
let bFilter = new bloomFilter({
optimize: true,/*This automatically calculates number of hashes and bits to be used internally*/
falsePositiveRate: 0.001,/*Desired false positive rate,less rate will use more memory internally*/
isCounting: false,// False by default,
nElements:10000
});
To create a counting bloom Filter that supports deletions as well, just pass
let bFilter = new bloomFilter({
optimize: true,/*This automatically calculates number of hashes and bits to be used internally*/
falsePositiveRate: 0.001,/*Desired false positive rate,less rate will use more memory internally*/
isCounting: true,// False by default,
nElements:10000
});
Add an element
bFilter.add('hello world');
Test for membership
if(bFilter.has('hello world')===true){
console.log('Present, but may be a false positive');
}else{
console.log('Not present definitely');
}
Delete
This is available only for couting bloom filters
bFilter.delete('hello world');
Serialization and Deserialization
let bFilterArrayBuffer=bFilter.serialize();
let newFilter=new bloomFilter({},bFilterArrayBuffer);
newFilter.add('hello, i am the best bloom filter');
On resize
bFilter.on('resized',(bitsPerCounter)=>{
console.log('bits per counter',bitsPerCounter);
});
Test
To test: npm run test
Acknowledgements
- Hat tip to anyone who uses and contributes to the code....
- Purav Aggarwal :)