bloom-filters

A ScalableBloomFilter is a variant of a Bloom Filter that adapts dynamically to the number of elements stored while maintaining a maximum false positive probability. It achieves this by adding new PartitionBloomFilter instances as the current filter reaches its capacity (load factor >= 0.5).

Key Characteristics

• Dynamic Growth: Automatically adds new filters when the current one is full.
• Error Rate Tightening: Each new filter added has a reduced error rate controlled by a _ratio to ensure the cumulative false positive probability remains bounded.
• Capacity: The total capacity is the sum of the capacities of all internal filters.
• False Positive Rate: The overall rate is the product of the rates of all internal filters.

import ScalableBloomFilter from 'bloom-filters/scalable-bloom-filter';

// Create a filter with initial size 128 and error rate 0.001
const filter = new ScalableBloomFilter(128, 0.001);

// Add elements
filter.add('my-element');

// Check for existence
if (filter.has('my-element')) {
  console.log('Element found!');
}

The XorFilter is a high-performance, static membership filter designed for fixed sets of elements. It is highly space-efficient but, unlike standard Bloom Filters, it is not incremental. You must provide the entire set of elements at once to build the filter. Once built, it provides fast has() checks to determine if an element might be in the set.

Key Constraints:

• Static Only: You cannot add elements one by one after the filter is created. The add() method must be called with an array of elements exactly matching the size provided in the constructor.
• Uniqueness: The input array to add() must contain unique values. Duplicates will cause an error.
• Fingerprint Sizes: You can choose the fingerprint length (bits per fingerprint) to balance space efficiency and false positive rates. Supported sizes are 8, 16, 32, or 64 bits.

import XorFilter from 'bloom-filters/xor-filter.js';

// Option 1: Create and add elements manually
let xor = new XorFilter(3, 16); // size=3, 16-bit fingerprints
xor.add(['a', 'b', 'c']);
console.log(xor.has('a')); // true
console.log(xor.has('d')); // false

// Option 2: Use the static create() method (Recommended)
const xor = XorFilter.create(['a', 'b', 'c'], 16);
console.log(xor.has('a')); // true

The MinHash class implements a locality-sensitive hashing scheme to estimate the Jaccard similarity coefficient between two large sets of numbers.

Important: To get accurate results, you must only compare MinHash instances that were produced using the same MinHashFactory (or at least the same number of hash functions and identical HashFunction parameters). Comparing MinHashes with different hash functions will yield incorrect similarity estimates.

Key Methods:

• add(value: number): Inserts a single number into the MinHash and updates its signature.
• bulkLoad(values: number[]): Efficiently ingests an array of numbers to update the signature.
• compareWith(other: MinHash): Returns the estimated Jaccard similarity coefficient (a value between 0 and 1). Throws EmptyMinHashError if either MinHash is empty.

import MinHash, { HashFunction } from 'bloom-filters';

const hashFunctions: HashFunction[] = [
  { a: 1, b: 2, c: 101 },
  { a: 3, b: 4, c: 103 }
];

const minhash1 = new MinHash(2, hashFunctions);
minhash1.add(10);
minhash1.add(20);

const minhash2 = new MinHash(2, hashFunctions);
minhash2.add(10);
minhash2.add(30);

const similarity = minhash1.compareWith(minhash2);
console.log(`Estimated similarity: ${similarity}`);

A Counting Bloom filter tracks insertions and deletions by using small counters instead of single bits. This allows for the removal of elements.

Methods:

• add(element: HashableInput): Add an element.
• remove(element: HashableInput): Delete an element (returns true if successful, false otherwise).
• has(element: HashableInput): Test for membership.
• equals(other: CountingBloomFilter): Compare equality.
• rate(): Return the 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)

A XOR Filter is a highly space-efficient probabilistic data structure, ideal for read-only sets. It is generally faster and smaller than both Bloom and Cuckoo filters.

Implementation Details:

• Supports 8-bit and 16-bit fingerprint lengths.
• Uses Buffers internally, which are exported/imported as base64 strings.
• Input Types: Accepts HashableInput or Long.

Methods:

• add(elements: XorHashableInput[]): Adds elements to the filter. Note: Calling this method more than once will override the current filter with the new elements.
• has(element: XorHashableInput): Returns true if the element is in the set, false otherwise.

const {XorFilter} = require('bloom-filters')
const xor8 = new XorFilter(1)
xor8.add(['a'])
xor8.has('a') // true
xor8.has('b') // false
// or the combined
const filter = XorFilter.create(['a'])
filter.has('a') // true
// using 16-bits fingerprint length
XorFilter.create(['a'], 16).has('a') // true
const a = new XorFilter(1, 16)
a.add(['a'])
a.has('a') // true

A Scalable Bloom Filter dynamically adapts to the number of elements stored while maintaining a maximum false positive probability. It uses Partitioned Bloom Filters internally.

Methods:

• add(element: HashableInput): Add an element.
• has(element: HashableInput): Test for membership.
• equals(other: ScalableBloomFilter): Compare equality.
• capacity(): Return the total capacity.
• rate(): Return the current error rate of the internal filter being used.

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