t-digest

The implementation in this library is based on the MergingDigest described in Computing Extremely Accurate Quantiles Using t-Digests by Ted Dunning and Otmar Ertl.

The implementation in this library has a few differences from the reference implementation associated with that paper:

Merge does not modify the input
Derialization similar to other sketches in this library, although reading the reference implementation format is supported

Unlike all other algorithms in the library, t-digest is empirical and has no mathematical basis for estimating its error and its results are dependent on the input data. However, for many common data distributions, it can produce excellent results. t-digest also operates only on numeric data and, unlike the quantiles family algorithms in the library which return quantile approximations from the input domain, t-digest interpolates values and will hold and return data points not seen in the input.

The closest alternative to t-digest in this library is REQ sketch. It prioritizes one chosen side of the rank domain: either low rank accuracy or high rank accuracy. t-digest (in this implementation) prioritizes both ends of the rank domain and has lower accuracy towards the middle of the rank domain (median).

Measurements show that t-digest is slightly biased (tends to underestimate low ranks and overestimate high ranks), while still doing very well close to the extremes. The effect seems to be more pronounced with more input values.

For more information on the performance characteristics, see the Datasketches page on t-digest.

class tdigest_float(*args, **kwargs)

Static Methods:

deserialize(bytes: bytes) → _datasketches.tdigest_float: Deserializes the sketch from a bytes object.

Non-static Methods:

__init__(self, k: int = 200) → None

Creates a tdigest instance with the given value of k.

Parameters:: k (int, optional) – Controls the size/accuracy trade-off of the sketch. Default is 200.

compress: Process buffered values and merge centroids, if necesssary

get_cdf: Returns an approximation to the Cumulative Distribution Function (CDF), which is the cumulative analog of the PMF, of the input stream given a set of split points (values). If the sketch is empty this returns an empty vector. split_points is an array of m unique, monotonically increasing float values that divide the real number line into m+1 consecutive disjoint intervals. It is not necessary to include either the min or max values in these split points.

get_max_value: Returns the maximum value from the stream. If empty, throws a RuntimeError

get_min_value: Returns the minimum value from the stream. If empty, throws a RuntimeError

get_pmf: Returns an approximation to the Probability Mass Function (PMF) of the input stream given a set of split points (values). If the sketch is empty this returns an empty vector. split_points is an array of m unique, monotonically increasing float values that divide the real number line into m+1 consecutive disjoint intervals. It is not necessary to include either the min or max values in these split points.

get_quantile: Returns an approximation to the data value associated with the given rank in a hypothetical sorted version of the input stream so far.

get_rank: Computes the approximate normalized rank of the given value

get_serialized_size_bytes: Returns the size of the serialized sketch, in bytes

get_total_weight: The total weight processed by the sketch

is_empty: Returns True if the sketch is empty, otherwise False

property k: The configured parameter k

merge: Merges the provided sketch into this one

serialize: Serializes the sketch into a bytes object.

to_string: Produces a string summary of the sketch

update

Overloaded function.

update(self, item: float) -> None

Updates the sketch with the given value

update(self, array: ndarray[dtype=float32]) -> None

Updates the sketch with the values in the given array

class tdigest_double(*args, **kwargs)