ThetaSketch
Defined in: packages/distillate/src/theta/theta.ts:68
A Theta sketch: counts distinct keys exactly up to k, and past that
estimates from the k smallest key hashes, within about 1 / sqrt(k).
Hashes live in a table of up to 2k slots. Once it is full to 3/4, a
quickselect keeps the k smallest and lowers theta to the next, so a key
hashing above theta is rejected without touching the table (QuickSelect, as
in Apache DataSketches).
When those rebuilds run depends on the order keys arrive in, so the table
itself does not. Every rebuild’s theta is the (k+1)-th smallest hash seen so
far, never below the true one, so the table always holds the true k
smallest. Every read goes through that canonical sample: the k smallest
hashes, theta the next. Equal key sets then answer alike whatever the order.
Example
Section titled “Example”const sketch = ThetaSketch.create(0.02);sketch.add("alice");Constructors
Section titled “Constructors”Constructor
Section titled “Constructor”new ThetaSketch(
params?):ThetaSketch
Defined in: packages/distillate/src/theta/theta.ts:89
Creates a sketch at an explicit k.
Parameters
Section titled “Parameters”params?
Section titled “params?”ThetaParams = {}
Sample size and optional hash seed.
Returns
Section titled “Returns”ThetaSketch
Accessors
Section titled “Accessors”isEmpty
Section titled “isEmpty”Get Signature
Section titled “Get Signature”get isEmpty():
boolean
Defined in: packages/distillate/src/theta/theta.ts:261
Whether no key has been added.
Returns
Section titled “Returns”boolean
isEstimating
Section titled “isEstimating”Get Signature
Section titled “Get Signature”get isEstimating():
boolean
Defined in: packages/distillate/src/theta/theta.ts:266
Whether count() estimates rather than counts.
Returns
Section titled “Returns”boolean
Get Signature
Section titled “Get Signature”get k():
number
Defined in: packages/distillate/src/theta/theta.ts:240
Hashes kept once the sketch is estimating.
Returns
Section titled “Returns”number
retained
Section titled “retained”Get Signature
Section titled “Get Signature”get retained():
number
Defined in: packages/distillate/src/theta/theta.ts:256
Hashes the estimate is computed from, at most k.
Returns
Section titled “Returns”number
Get Signature
Section titled “Get Signature”get seed():
number
Defined in: packages/distillate/src/theta/theta.ts:245
Hash seed the sketch was built with.
Returns
Section titled “Returns”number
Get Signature
Section titled “Get Signature”get theta():
number
Defined in: packages/distillate/src/theta/theta.ts:250
Fraction of the hash range sampled, in (0, 1]; 1 while exact.
Returns
Section titled “Returns”number
Methods
Section titled “Methods”add(
key):void
Defined in: packages/distillate/src/theta/theta.ts:275
Records a key. Adding a key already seen leaves the sketch unchanged.
Parameters
Section titled “Parameters”BytesLike
The key to record.
Returns
Section titled “Returns”void
count()
Section titled “count()”count():
number
Defined in: packages/distillate/src/theta/theta.ts:306
Counts the distinct keys added: exact while not isEstimating.
Returns
Section titled “Returns”number
The distinct count, or its estimate.
difference()
Section titled “difference()”difference(
other):ThetaSketch
Defined in: packages/distillate/src/theta/theta.ts:421
Subtracts a sketch from this one, giving a sketch of the keys this one has seen and the other has not. Both are left untouched.
Parameters
Section titled “Parameters”ThetaSketch
The sketch to subtract; must share this one’s seed.
Returns
Section titled “Returns”ThetaSketch
A new sketch of the difference, at the smaller k.
Throws
Section titled “Throws”ParamError if the seeds differ.
equals()
Section titled “equals()”equals(
other):boolean
Defined in: packages/distillate/src/theta/theta.ts:453
Whether two sketches hold the same canonical sample at the same k and
seed. The order keys arrived in does not enter into it.
Parameters
Section titled “Parameters”ThetaSketch
The sketch to compare against.
Returns
Section titled “Returns”boolean
true if the two would answer every query identically.
intersect()
Section titled “intersect()”intersect(
other):ThetaSketch
Defined in: packages/distillate/src/theta/theta.ts:386
Intersects two sketches, giving a sketch of the keys both have seen. Both
are left untouched. Two disjoint sets read 0, with an upper bound above
it: a sample cannot rule out a small overlap.
Parameters
Section titled “Parameters”ThetaSketch
The sketch to intersect with; must share this one’s seed.
Returns
Section titled “Returns”ThetaSketch
A new sketch of the intersection, at the smaller k.
Throws
Section titled “Throws”ParamError if the seeds differ.
lowerBound()
Section titled “lowerBound()”lowerBound(
sd):number
Defined in: packages/distillate/src/theta/theta.ts:319
A lower bound on the distinct count, at sd standard deviations. Over
many sketches the two bounds together hold about as often as a normal
interval of that width: 68%, 95% and 99.7%.
Parameters
Section titled “Parameters”number
Standard deviations: 1, 2 or 3.
Returns
Section titled “Returns”number
The bound; count() while exact.
Throws
Section titled “Throws”ParamError for any other sd.
toBytes()
Section titled “toBytes()”toBytes():
Uint8Array
Defined in: packages/distillate/src/theta/theta.ts:199
Serializes the sketch’s canonical sample to a portable little-endian byte layout.
Returns
Section titled “Returns”Uint8Array
The serialized sketch, readable by ThetaSketch.fromBytes.
toJSON()
Section titled “toJSON()”toJSON():
FilterJSON
Defined in: packages/distillate/src/theta/theta.ts:225
Serializes the sketch to a JSON-safe envelope wrapping ThetaSketch.toBytes.
Returns
Section titled “Returns”The envelope, readable by ThetaSketch.fromJSON.
union()
Section titled “union()”union(
other):ThetaSketch
Defined in: packages/distillate/src/theta/theta.ts:349
Merges two sketches, giving a sketch of the keys either has seen. Both are left untouched.
The result keeps the smaller k, as HLL keeps the coarser precision:
with the larger, a union cut to a small k before a third sketch joins
would differ from one cut after, and grouping would change the answer.
Parameters
Section titled “Parameters”ThetaSketch
The sketch to merge with; must share this one’s seed.
Returns
Section titled “Returns”ThetaSketch
A new sketch of the union, which takes keys and further operations.
Throws
Section titled “Throws”ParamError if the seeds differ, since the same key would then hash differently on each side.
upperBound()
Section titled “upperBound()”upperBound(
sd):number
Defined in: packages/distillate/src/theta/theta.ts:332
An upper bound on the distinct count, at sd standard deviations. Over
many sketches the two bounds together hold about as often as a normal
interval of that width: 68%, 95% and 99.7%.
Parameters
Section titled “Parameters”number
Standard deviations: 1, 2 or 3.
Returns
Section titled “Returns”number
The bound; count() while exact.
Throws
Section titled “Throws”ParamError for any other sd.
create()
Section titled “create()”
staticcreate(relativeError):ThetaSketch
Defined in: packages/distillate/src/theta/theta.ts:111
Creates a sketch whose standard error meets relativeError.
Parameters
Section titled “Parameters”relativeError
Section titled “relativeError”number
Target relative error, e.g. 0.01 for 1%.
Returns
Section titled “Returns”ThetaSketch
A new, empty sketch.
from()
Section titled “from()”
staticfrom(keys,relativeError):ThetaSketch
Defined in: packages/distillate/src/theta/theta.ts:122
Creates a sketch counting keys, sized to meet relativeError.
Parameters
Section titled “Parameters”Iterable<BytesLike>
The keys to record.
relativeError
Section titled “relativeError”number
Target relative error, e.g. 0.01 for 1%.
Returns
Section titled “Returns”ThetaSketch
A new sketch holding every key.
fromBytes()
Section titled “fromBytes()”
staticfromBytes(bytes):ThetaSketch
Defined in: packages/distillate/src/theta/theta.ts:137
Restores a sketch from ThetaSketch.toBytes. It takes keys and set operations like the sketch it was written from.
Parameters
Section titled “Parameters”Uint8Array
The serialized sketch.
Returns
Section titled “Returns”ThetaSketch
The reconstructed sketch.
fromJSON()
Section titled “fromJSON()”
staticfromJSON(value):ThetaSketch
Defined in: packages/distillate/src/theta/theta.ts:235
Restores a sketch from its ThetaSketch.toJSON envelope.
Parameters
Section titled “Parameters”unknown
The parsed envelope.
Returns
Section titled “Returns”ThetaSketch
The reconstructed sketch.