TopK
Defined in: packages/data/src/probabilistic/top-k.ts:39
Approximate heavy hitters: the k most frequent items in a stream.
A CountMinSketch estimates every item’s frequency in fixed space; on
its own it cannot say which items are frequent, because it never stores
them. This pairs it with a bounded set of candidates — the k items with the
highest estimates seen so far — which is what turns “how often was X seen”
into “what is seen most”.
Both approximations compound: an item is reported with the sketch’s
over-estimate, and a genuinely heavy item can be missed if it was evicted
from the candidate set early, before its count grew. Raising k above the
number actually wanted makes that far less likely.
Time complexity: O(depth + k) per add — the sketch update plus a scan of
the candidates. heavyHitters is O(k log k) to sort.
Type Parameters
Section titled “Type Parameters”T
The item type.
Constructors
Section titled “Constructors”Constructor
Section titled “Constructor”new TopK<
T>(options):TopK<T>
Defined in: packages/data/src/probabilistic/top-k.ts:47
Parameters
Section titled “Parameters”options
Section titled “options”TopKOptions<T>
Returns
Section titled “Returns”TopK<T>
Properties
Section titled “Properties”
readonlyk:number
Defined in: packages/data/src/probabilistic/top-k.ts:45
How many heavy hitters are tracked.
Methods
Section titled “Methods”add(
item,times?):void
Defined in: packages/data/src/probabilistic/top-k.ts:72
O(depth + k).
Parameters
Section titled “Parameters”T
times?
Section titled “times?”number = 1
Returns
Section titled “Returns”void
addAll()
Section titled “addAll()”addAll(
items,times?):void
Defined in: packages/data/src/probabilistic/top-k.ts:98
O(m·(depth + k)) 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/top-k.ts:66
Returns
Section titled “Returns”void
count()
Section titled “count()”count():
number
Defined in: packages/data/src/probabilistic/top-k.ts:62
How many candidates are currently tracked, at most k.
Returns
Section titled “Returns”number
estimate()
Section titled “estimate()”estimate(
item):number
Defined in: packages/data/src/probabilistic/top-k.ts:105
The sketch’s estimate for item, tracked or not. O(depth).
Parameters
Section titled “Parameters”T
Returns
Section titled “Returns”number
heavyHitters()
Section titled “heavyHitters()”heavyHitters():
HeavyHitter<T>[]
Defined in: packages/data/src/probabilistic/top-k.ts:120
The tracked heavy hitters, most frequent first. O(k log k).
Counts are re-read from the sketch, so they are current rather than whatever they were when the candidate was admitted.
Returns
Section titled “Returns”HeavyHitter<T>[]
isTracked()
Section titled “isTracked()”isTracked(
item):boolean
Defined in: packages/data/src/probabilistic/top-k.ts:110
Whether item is currently one of the tracked candidates. O(1).
Parameters
Section titled “Parameters”T
Returns
Section titled “Returns”boolean
total()
Section titled “total()”total():
number
Defined in: packages/data/src/probabilistic/top-k.ts:57
The total of every count added, exact.
Returns
Section titled “Returns”number