Bloom-Filters

JavaScript/TypeScript implementation of probabilistic data structures: Bloom Filter (and its derived), HyperLogLog, Count-Min Sketch, Top-K and MinHash. This package relies on non-cryptographic hash functions.

📕Online documentation

Keywords: bloom filter, cuckoo filter, KyperLogLog, MinHash, Top-K, probabilistic data-structures, XOR-Filter.

❗️Compatibility❗️

• Be carefull when migrating from a version to another.
• Bug fixes were introduced in 1.3.7 and from 1.3.9 to 2.0.0+ for hashing and indexing data. Then, you must re-build completely your filters from start to be compatible with the new versions.
• To keep the breaking changes rule of npm versions we will make now new majored versions since 1.3.9 whenever a modification is done on the hashing/indexing system or breaks the current API.

Table of contents

• Installation
• Data structures
• Classic Bloom Filter
• Partitioned Bloom Filter
• Scalable Bloom Filter
• Cuckoo Filter
• Counting Bloom Filter
• Count Min Sketch
• HyperLogLog
• MinHash
• Top-K
• Invertible Bloom Filters
• XOR-Filter
• Export and import
• Seeding and Hashing
• Documentation
• Tests
• References
• Changelog
• License

Installation

npm install bloom-filters --save

Supported platforms

• Node.js: v4.0.0 or higher
• Google Chrome: v41 or higher
• Mozilla Firefox: v34 or higher
• Microsoft Edge: v12 or higher

Data structures

Classic Bloom Filter

A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not.

Reference: Bloom, B. H. (1970). Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7), 422-426. (Full text article)

Methods

• add(element: HashableInput) -> void: add an element into the filter.
• has(element: HashableInput) -> 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).

const {BloomFilter} = require('bloom-filters')
// 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)

Partitioned Bloom Filter

A Partitioned Bloom Filter is a variation of a classic Bloom Filter.

This filter works by partitioning the M-sized bit array into k slices of size m = M/k bits, k = nb of hash functions in the filter. Each hash function produces an index over m for its respective slice. Thus, each element is described by exactly k bits, meaning the distribution of false positives is uniform across all elements.

Be careful, as a Partitioned Bloom Filter have much higher collison risks that a classic Bloom Filter on small sets of data.

Reference: Chang, F., Feng, W. C., & Li, K. (2004, March). Approximate caches for packet classification. In INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies (Vol. 4, pp. 2196-2207). IEEE. (Full text article)

Methods

• add(element: HashableInput) -> void: add an element into the filter.
• has(element: HashableInput) -> 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).

const {PartitionedBloomFilter} = require('bloom-filters')

// 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)

// add some value in the filter
filter.add('alice')
filter.add('bob')

// lookup for some data
console.log(filter.has('bob')) // output: true
console.log(filter.has('daniel')) // output: false

// now use it like a classic bloom 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)

Scalable Bloom Filter

A Scalable Bloom Filter is a variant of Bloom Filters that can adapt dynamically to the number of elements stored, while assuring a maximum false positive probability

Reference: ALMEIDA, Paulo Sérgio, BAQUERO, Carlos, PREGUIÇA, Nuno, et al. Scalable bloom filters. Information Processing Letters, 2007, vol. 101, no 6, p. 255-261. (Full text article)

This filter use internally Paritionned Bloom Filters.

Methods

• add(element: HashableInput) -> void: add an element into the filter.
• has(element: HashableInput) -> 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: ScalableBloomFilter) -> boolean: Test if two filters are equals.
• capacity():number -> return the total capacity of this filter
• rate() -> number: compute the filter's false positive rate (or error rate).

const {ScalableBloomFilter} = require('bloom-filters')

// by default it creates an ideally scalable bloom filter for 8 elements with an error rate of 0.01 and a load factor of 0.5
const filter = new ScalableBloomFilter()
filter.add('alice')
filter.add('bob')
filter.add('carl')
for (let i = 0; i < 10000; i++) {
  filter.add('elem:' + i)
}
filter.has('somethingwrong') // false

filter.capacity() // total capacity
filter.rate() // current rate of the current internal filter used

Cuckoo Filter

Cuckoo filters improve on Bloom filters by supporting deletion, limited counting, and bounded False positive rate with similar storage efficiency as a standard Bloom Filter.

Reference: Fan, B., Andersen, D. G., Kaminsky, M., & Mitzenmacher, M. D. (2014, December). Cuckoo filter: Practically better than bloom. In Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies (pp. 75-88). ACM. (Full text article)

Methods

• add(element: HashableInput) -> void: add an element into the filter.
• remove(element: HashableInput) -> boolean: delete an element from the filter, returning True if the deletion was a success and False otherwise.
• has(element: HashableInput) -> 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).

const {CuckooFilter} = require('bloom-filters')

// create a Cuckoo Filter with size = 15, fingerprint length = 3 and bucket size = 2
const filter = new CuckooFilter(15, 3, 2)
filter.add('alice')
filter.add('bob')

// lookup for some data
console.log(filter.has('bob')) // output: true
console.log(filter.has('daniel')) // output: false

// remove something
filter.remove('bob')
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)

WARNING: The error rate cannot be higher than 1 * 10^-18. Above this value, you will get an exception stating that the fingerprint length is higher than the hash length.

Counting Bloom Filter

A Counting Bloom filter works in a similar manner as a regular Bloom filter; however, it is able to keep track of insertions and deletions. In a counting Bloom filter, each entry in the Bloom filter is a small counter associated with a basic Bloom filter bit.

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: HashableInput) -> void: add an element into the filter.
• remove(element: HashableInput) -> boolean: delete an element from the filter, returning True if the deletion was a success and False otherwise.
• has(element: HashableInput) -> 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).

const CountingBloomFilter = require('bloom-filters').CountingBloomFilter

// create a Bloom Filter with capacity = 15 and 4 hash functions
let filter = new CountingBloomFilter(15, 4)

// add some value in the filter
filter.add('alice')
filter.add('bob')
filter.add('carole')

// remove some value
filter.remove('carole')

// lookup for some data
console.log(filter.has('bob')) // output: true
console.log(filter.has('carole')) // output: false
console.log(filter.has('daniel')) // output: false

// print false positive rate (around 0.1)
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)

Count Min Sketch

The Count Min Sketch (CM sketch) is a probabilistic data structure that serves as a frequency table of events in a stream of data. It uses hash functions to map events to frequencies, but unlike a hash table uses only sub-linear space, at the expense of overcounting some events due to collisions.

Reference: Cormode, G., & Muthukrishnan, S. (2005). An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1), 58-75. (Full text article)

Methods

• update(element: HashableInput, count = 1) -> void: add count occurences of an element into the sketch.
• count(element: HashableInput) -> number: estimate the number of occurences of an element.
• merge(other: CountMinSketch) -> CountMinSketch: merge occurences of two sketches.
• equals(other: CountMinSketch) -> boolean: Test if two sketchs are equals.
• clone(): CountMinSketch: Clone the sketch.

const {CountMinSketch} = require('bloom-filters')

// create a new Count Min sketch with 2048 columns and 1 row
const sketch = new CountMinSketch(2048, 1)

// push some occurrences in the sketch
sketch.update('alice')
sketch.update('alice')
sketch.update('bob')

// count occurrences
console.log(sketch.count('alice')) // output: 2
console.log(sketch.count('bob')) // output: 1
console.log(sketch.count('daniel')) // output: 0

// 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)

HyperLogLog

HyperLogLog is an algorithm for the count-distinct problem, approximating the number of distinct elements in a multiset. Calculating the exact cardinality of a multiset requires an amount of memory proportional to the c