HyperLogLog
Defined in: packages/data/src/probabilistic/hyper-log-log.ts:39
Estimates how many distinct items a stream contained, in memory that does not grow with the answer.
A Set answers exactly and costs O(distinct); this answers approximately and
costs 2 ** precision bytes whether the stream held a thousand items or a
billion. Use it when the cardinality is large, approximate is acceptable, and
the exact members are not needed afterwards — they cannot be recovered. The
estimate is never exact, not even for a handful of items.
The estimator is the standard one: hash each item, take the low precision
bits as a register index, count the leading zeros of the rest, and keep the
maximum per register. The harmonic mean of 2 ** register across registers
is proportional to the cardinality; the small-range correction (linear
counting over the empty registers) covers the regime where the raw estimate
is biased.
Time complexity: O(1) per add, O(2 ** precision) per count. The estimate
is stable — adding the same item twice changes nothing.
Type Parameters
Section titled “Type Parameters”T
The item type.
Constructors
Section titled “Constructors”Constructor
Section titled “Constructor”new HyperLogLog<
T>(iterable,options):HyperLogLog<T>
Defined in: packages/data/src/probabilistic/hyper-log-log.ts:49
Parameters
Section titled “Parameters”iterable
Section titled “iterable”Iterable<T, any, any> | undefined
options
Section titled “options”Returns
Section titled “Returns”HyperLogLog<T>
Properties
Section titled “Properties”registerCount
Section titled “registerCount”
readonlyregisterCount:number
Defined in: packages/data/src/probabilistic/hyper-log-log.ts:47
The number of registers, 2 ** precision.
Accessors
Section titled “Accessors”relativeError
Section titled “relativeError”Get Signature
Section titled “Get Signature”get relativeError():
number
Defined in: packages/data/src/probabilistic/hyper-log-log.ts:73
The relative error to expect, as a fraction: 1.04 / sqrt(registers).
Returns
Section titled “Returns”number
Methods
Section titled “Methods”add(
item):void
Defined in: packages/data/src/probabilistic/hyper-log-log.ts:82
O(1). Adding an item already seen leaves the estimate unchanged.
Parameters
Section titled “Parameters”T
Returns
Section titled “Returns”void
addAll()
Section titled “addAll()”addAll(
items):void
Defined in: packages/data/src/probabilistic/hyper-log-log.ts:102
O(m) in the number of items.
Parameters
Section titled “Parameters”Iterable<T>
Returns
Section titled “Returns”void
clear()
Section titled “clear()”clear():
void
Defined in: packages/data/src/probabilistic/hyper-log-log.ts:77
Returns
Section titled “Returns”void
count()
Section titled “count()”count():
number
Defined in: packages/data/src/probabilistic/hyper-log-log.ts:118
The estimated number of distinct items. O(registerCount).
Never exact, at any cardinality. Below ~2.5·registers linear counting takes
over and is very close — but two items hashing to the same register are
indistinguishable there too, so a handful of items can still estimate one
or two low. Above that the harmonic-mean estimator lands within
relativeError about 65% of the time and twice that about 95% of the
time.
Returns
Section titled “Returns”number
merge()
Section titled “merge()”merge(
other):void
Defined in: packages/data/src/probabilistic/hyper-log-log.ts:155
Folds other in, so this estimator covers the union of both streams.
Merging is lossless — the union’s registers are the element-wise maxima — which is what lets partitions be counted independently and combined.
Parameters
Section titled “Parameters”HyperLogLog<T>
Returns
Section titled “Returns”void
Throws
Section titled “Throws”If the two were built with different precisions.