T-Digest Functions

Presto implements two algorithms for estimating rank-based metrics, quantile digest and T-digest. T-digest has better performance in general while the Presto implementation of quantile digests supports more numeric types. T-digest has better accuracy at the tails, often dramatically better, but may have worse accuracy at the median, depending on the compression factor used. In comparison, quantile digests supports a maximum rank error, which guarantees relative uniformity of precision along the quantiles. Quantile digests are also formally proven to support lossless merges, while T-digest is not (but does empirically demonstrate lossless merges).

T-digest was developed by Ted Dunning.

Data Structures

A T-digest is a data sketch which stores approximate percentile information. The Presto type for this data structure is called tdigest, and it accepts a parameter of type double which represents the set of numbers to be ingested by the tdigest. Other numeric types may be added in a future release.

T-digests may be merged without losing precision, and for storage and retrieval they may be cast to/from VARBINARY.

Functions

merge(tdigest<double>) → tdigest<double>

Merges all input tdigests into a single tdigest.

value_at_quantile(tdigest<double>, quantile) → double

Returns the approximate percentile values from the T-digest given the number quantile between 0 and 1.

quantile_at_value(tdigest<double>, value) → double

Returns the approximate quantile number between 0 and 1 from the T-digest given an input value. Null is returned if the T-digest is empty or the input value is outside of the range of the digest.

scale_tdigest(tdigest<double>, scale_factor) → tdigest<double>

Returns a tdigest whose distribution has been scaled by a factor specified by scale_factor.

values_at_quantiles(tdigest<double>, quantiles) → array<double>

Returns the approximate percentile values as an array given the input T-digest and array of values between 0 and 1 which represent the quantiles to return.

trimmed_mean(tdigest<double>, lower_quantile, upper_quantile) → double

Returns an estimate of the mean, excluding portions of the distribution outside the provided quantile bounds. Both lower_quantile and upper_quantile must be between 0 and 1.

tdigest_agg(x) → tdigest<double>

Returns the tdigest which is composed of all input values of x.

tdigest_agg(x, w) → tdigest<double>

Returns the tdigest which is composed of all input values of x using the per-item weight w.

tdigest_agg(x, w, compression) → tdigest<double>

Returns the tdigest which is composed of all input values of x using the per-item weight w and compression factor compression. compression must be a value greater than zero, and it must be constant for all input rows.

Compression factor of 500 is a good starting point that typically yields good accuracy and performance.

destructure_tdigest(tdigest<double>) → row<centroid_means array<double>, centroid_weights array<integer>, compression double, min double, max double, sum double, count bigint>

Returns a row that represents a tdigest data structure in the form of its component parts. These include arrays of the centroid means and weights, the compression factor, and the maximum, minimum, sum and count of the values in the digest.

construct_tdigest(centroid_means array<double>, centroid_weights array<double>, compression double, min double, max double, sum double, count bigint) → tdigest<double>

Returns the tdigest from its component parts (arrays of the centroid means and weights, the compression factor, and the maximum, minimum, sum and count of the values in the digest). This is an inverse of destructure_tdigest.

This function is particularly useful for adding externally-created tdigests to Presto.