CountMinSketch
Defined in: packages/data/src/probabilistic/count-min-sketch.ts:39
Approximate frequency counting: how many times was this item seen?
A Map<T, number> answers exactly and costs O(distinct); this answers with a
bounded over-estimate in width × depth counters, fixed regardless of how
many distinct items pass through. That is what makes it usable on a stream
whose alphabet does not fit in memory.
Estimates never under-count. Every row’s counter for an item includes
that item’s true count plus whatever collided with it, so the minimum across
rows is an upper bound. With the default sizing, the over-estimate exceeds
epsilon × total with probability at most delta.
There is no way to remove an item or to enumerate what was counted — the items themselves are never stored.
Time complexity: O(depth) for add and estimate, independent of the
stream’s length. Space: width × depth 32-bit counters.
Type Parameters
Section titled “Type Parameters”T
The item type.
Constructors
Section titled “Constructors”Constructor
Section titled “Constructor”new CountMinSketch<
T>(options):CountMinSketch<T>
Defined in: packages/data/src/probabilistic/count-min-sketch.ts:51
Parameters
Section titled “Parameters”options
Section titled “options”Returns
Section titled “Returns”CountMinSketch<T>
Properties
Section titled “Properties”
readonlydepth:number
Defined in: packages/data/src/probabilistic/count-min-sketch.ts:46
Rows, i.e. independent hashes.
readonlywidth:number
Defined in: packages/data/src/probabilistic/count-min-sketch.ts:44
Counters per row.
Methods
Section titled “Methods”add(
item,times?):void
Defined in: packages/data/src/probabilistic/count-min-sketch.ts:84
Records times occurrences of item. O(depth).
Parameters
Section titled “Parameters”T
times?
Section titled “times?”number = 1
Returns
Section titled “Returns”void
Throws
Section titled “Throws”If times is negative or not an integer.
addAll()
Section titled “addAll()”addAll(
items,times?):void
Defined in: packages/data/src/probabilistic/count-min-sketch.ts:106
O(m·depth) in the number of items.
Parameters
Section titled “Parameters”Iterable<T>
times?
Section titled “times?”number = 1
Returns
Section titled “Returns”void
clear()
Section titled “clear()”clear():
void
Defined in: packages/data/src/probabilistic/count-min-sketch.ts:74
Returns
Section titled “Returns”void
estimate()
Section titled “estimate()”estimate(
item):number
Defined in: packages/data/src/probabilistic/count-min-sketch.ts:118
The estimated number of times item was added. O(depth).
Never below the true count; above it by at most epsilon × total() with
probability 1 - delta.
Parameters
Section titled “Parameters”T
Returns
Section titled “Returns”number
merge()
Section titled “merge()”merge(
other):void
Defined in: packages/data/src/probabilistic/count-min-sketch.ts:143
Folds other in, so this sketch covers both streams.
Merging is exact — counters add element-wise — which is what lets partitions be counted independently.
Parameters
Section titled “Parameters”CountMinSketch<T>
Returns
Section titled “Returns”void
Throws
Section titled “Throws”If the two were not sized identically.
total()
Section titled “total()”total():
number
Defined in: packages/data/src/probabilistic/count-min-sketch.ts:70
The sum of every count added. Exact, unlike a per-item estimate.
Returns
Section titled “Returns”number