Shameless plug. Just wrote a paper about this: https://arxiv.org/abs/2001.06561 Containing a survey of the most popular Latency Aggregation methods used in the industry (Prometheus Histograms, t-digest, HDR-Histogram, DD-sketch/histogram).
The Circllhist algorithm is interesting, but I get an uneasy feeling from the use of a _relative error_ measure to evaluate the performance of quantile estimation. Note that other authors don't use this measure. Dunning uses Mean Absolute Error in his latest T-digest paper: https://arxiv.org/pdf/1902.04023.pdf Cohen uses Normalized Root-Mean-Squared Error to evaluate sampling schemes, which are equally capable of est…
Relative error is a practical choice, since it allows to cover an extremely large value range (essentially all floating point numbers) with small size ( O(log(range)) ) and zero-configuration. You can't have that with bounding the absolute error.
Also the relative error is what you are interested in most of the time as a practitioner. (200ms+/-10ms; 1year+/-15days)
DDSketch uses relative error for estimation as well.
> If your latency values were clustered around a small range, [...] T-digest will be significantly more accurate.
That is correct!
One point of this example was to demonstrate that merged t-digest can have unbounded errors. In the t-digest paper it was speculated that merged digest have bounded error, but the proof was just more difficult. As it turns out, if you have heavy merges and an extremely large value range, you can get unbounded errors.