ScalableBloomFilter

Defined in: packages/distillate/src/scalable/scalable.ts:159

A Bloom filter that grows with its key count and keeps its false-positive rate under epsilon, for when the number of keys is not known up front.

It is a chain of Bloom stages. Stage i holds n * growth ** i keys at a false-positive target of epsilon * (1 - tightening) * tightening ** i; those targets sum to at most epsilon, however many stages open.

Example

const seen = ScalableBloomFilter.create(1000, 0.01);
seen.add("alice");
seen.has("alice"); // true

Constructors

Constructor

new ScalableBloomFilter(params): ScalableBloomFilter

Defined in: packages/distillate/src/scalable/scalable.ts:217

Parameters

params

ScalableBloomParams

The filter’s settings.

Returns

ScalableBloomFilter

Throws

ParamError if a setting is out of range, or the first stage would need more than 2^32 - 1 bits.

Accessors

bitsPerKey

Get Signature

get bitsPerKey(): number

Defined in: packages/distillate/src/scalable/scalable.ts:622

Analytic design bits-per-key, m / capacity.

Returns

number

capacity

Get Signature

get capacity(): number

Defined in: packages/distillate/src/scalable/scalable.ts:607

Keys the open stages hold between them before the next one opens.

Returns

number

count

Get Signature

get count(): number

Defined in: packages/distillate/src/scalable/scalable.ts:602

Keys added that the filter did not already hold.

Returns

number

epsilon

Get Signature

get epsilon(): number

Defined in: packages/distillate/src/scalable/scalable.ts:632

Target false-positive rate for the whole chain.

Returns

number

growth

Get Signature

get growth(): number

Defined in: packages/distillate/src/scalable/scalable.ts:637

Capacity multiplier from one stage to the next.

Returns

number

m

Get Signature

get m(): number

Defined in: packages/distillate/src/scalable/scalable.ts:617

Total bits across every stage.

Returns

number

seed

Get Signature

get seed(): number

Defined in: packages/distillate/src/scalable/scalable.ts:627

Hash seed shared by every stage.

Returns

number

stages

Get Signature

get stages(): number

Defined in: packages/distillate/src/scalable/scalable.ts:612

Number of open stages.

Returns

number

tightening

Get Signature

get tightening(): number

Defined in: packages/distillate/src/scalable/scalable.ts:642

False-positive target multiplier from one stage to the next.

Returns

number

Methods

add()

add(key): void

Defined in: packages/distillate/src/scalable/scalable.ts:357

Adds a key. A key the filter already holds is not counted again, so duplicates never use up a stage’s capacity.

Parameters

key

BytesLike

The key to insert, as a string or bytes.

Returns

void

Throws

RangeError if the next stage would need more than 2^32 - 1 bits; the filter is left unchanged and still answers queries.

equals()

equals(other): boolean

Defined in: packages/distillate/src/scalable/scalable.ts:459

Tests structural equality: identical settings, the same stages with the same counts, and identical bits, which is exactly when the two serialize to the same bytes. Which stage a key lands in depends on when it arrived, so two filters given the same keys in a different order can be unequal.

Parameters

other

ScalableBloomFilter

The filter to compare against.

Returns

boolean

true if the two filters are identical.

has()

has(key): boolean

Defined in: packages/distillate/src/scalable/scalable.ts:382

Tests whether a key is in the set.

Parameters

key

BytesLike

The key to test.

Returns

boolean

true if present (possibly a false positive); false guarantees absence.

rate()

rate(): number

Defined in: packages/distillate/src/scalable/scalable.ts:395

Estimates the chain’s current false-positive rate from each stage’s actual fill: a key is a false positive if any stage wrongly holds it, so this is 1 - prod(1 - (setBits / m) ** k). It rises as keys are added and stays under epsilon while every stage is within its capacity.

Returns

number

The estimated false-positive rate, in [0, 1].

toBytes()

toBytes(): Uint8Array

Defined in: packages/distillate/src/scalable/scalable.ts:551

Serializes the filter to a portable little-endian frame, DSTL type 6.

Returns

Uint8Array

The serialized filter, readable by ScalableBloomFilter.fromBytes.

toJSON()

toJSON(): FilterJSON

Defined in: packages/distillate/src/scalable/scalable.ts:587

Serializes the filter to a JSON-friendly envelope wrapping the base64 of ScalableBloomFilter.toBytes.

Returns

FilterJSON

The JSON envelope.

union()

union(other): ScalableBloomFilter

Defined in: packages/distillate/src/scalable/scalable.ts:413

Returns a new filter holding every key of this filter and other. Stage i of the result is the OR of both inputs’ stage i, and the result has the longer of the two chains. Each stage’s count becomes the smaller of its capacity and the two counts summed: an upper bound, so the merged chain opens its next stage early rather than late.

Parameters

other

ScalableBloomFilter

A filter built with identical settings.

Returns

ScalableBloomFilter

A new filter; neither input is changed.

Throws

ScalableParamMismatchError if any setting, or the geometry of a stage both filters have, differs.

create()

static create(n, epsilon, options?): ScalableBloomFilter

Defined in: packages/distillate/src/scalable/scalable.ts:179

Creates a filter whose first stage holds n keys, for a chain-wide false-positive target.

Parameters

n

number

Keys the first stage holds.

epsilon

number

Target false-positive rate for the whole chain.

options?

ScalableBloomOptions = {}

Optional growth, tightening and seed.

Returns

ScalableBloomFilter

A new, empty filter.

from()

static from(keys, epsilon, options?): ScalableBloomFilter

Defined in: packages/distillate/src/scalable/scalable.ts:197

Builds a filter from keys, with the first stage sized for their count; it keeps growing as more keys arrive. Duplicates only oversize the first stage, since a key already held is not counted again.

Parameters

keys

Iterable<BytesLike>

The keys to insert.

epsilon

number

Target false-positive rate for the whole chain.

options?

ScalableBloomOptions = {}

Optional growth, tightening and seed.

Returns

ScalableBloomFilter

A new filter containing every key.

fromBytes()

static fromBytes(bytes): ScalableBloomFilter

Defined in: packages/distillate/src/scalable/scalable.ts:482

Restores a filter from its ScalableBloomFilter.toBytes serialization.

Parameters

bytes

Uint8Array

A frame produced by toBytes.

Returns

ScalableBloomFilter

The reconstructed filter.

Throws

SerializationError (or a subclass) if the frame is malformed.

fromJSON()

static fromJSON(value): ScalableBloomFilter

Defined in: packages/distillate/src/scalable/scalable.ts:597

Restores a filter from its ScalableBloomFilter.toJSON envelope.

Parameters

value

unknown

The JSON envelope.

Returns

ScalableBloomFilter

The reconstructed filter.