folly::TDigest

TDigests are a biased quantile estimator designed to estimate the values of the quantiles of streaming data with high accuracy and low memory, particularly for quantiles at the tails (p0.1, p1, p99, p99.9). See https://github.com/tdunning/t‐digest/blob/master/docs/t‐digest‐paper/histo.pdf for an explanation of what the purpose of TDigests is, and how they work.

Synopsis

Declared in <folly/stats/TDigest.h>

class TDigest;

Description

There is a notable difference between the implementation here and the implementation in the paper. In the paper, the recommended scaling function for bucketing centroids is an arcsin function. The arcsin function provides high accuracy for low memory, but comes at a relatively high compute cost. A good choice algorithm has the following properties:

The value of the function k(0, delta) = 0, and k(1, delta) = delta. This is a requirement for any t‐digest function.
The limit of the derivative of the function dk/dq at 0 is inf, and at 1 is inf. This provides bias to improve accuracy at the tails.
For any q <= 0.5, dk/dq(q) = dk/dq(1‐q). This ensures that the accuracy of upper and lower quantiles are equivalent. As such, TDigest uses a sqrt function with these properties, which is faster than arcsin. There is a small, but relatively negligible impact to accuracy at the tail. In empirical tests, accuracy of the sqrt approach has been adequate.

Types

Name

Description

Centroid

A single centroid holding a mean value and its weight.

MergeWorkingBuffer

Reusable scratch storage for in‐place merges.

Member Functions

Name

Description

TDigest [constructor]

Constructors

count

Returns the total weight of all values added to the digest.

empty

Returns whether the digest holds no centroids.

estimateCdf

Returns the estimate of the CDF at the given input. Raise an invalid_argument exception if the input is NaN or infinite. Returns NaN if the centroids are emtpy.

estimateQuantile

Estimates the value of the given quantile.

getCentroids

Returns the centroids that make up the digest.

max

Returns the maximum value added to the digest.

maxSize

Returns the maximum number of centroids retained after a merge.

mean

Returns the mean of all values added to the digest.

merge

merge overloads