tdunning/t-digest — pull request #3 by jpountz (2014-02-18 10:55:43+00:00)
Title: Improve accuracy of t-digest on small sets.

We plan on using t-digest to compute quantiles in a "SELECT quantiles(double_field, [0, 0.5, 0.9, 0.99]) GROUP BY some_term" fashion. However, since the distribution of the term we use to group by is often zipfian, some quantiles are computed on large sets while other quantiles are computed over very small sets.

Although we are very happy with the accuracy of t-digest over large sets, it is not so accurate on small sets although compression hasn't triggered any information loss. For example, if you add values 0, 1, 2, 3 and 4 to a TDigest instance, it will return 0.75 instead of 1 for q=0.25 and 4.5 instead of 4 for q=1.0.

The commit attached to this pull request proposes changes that would make t-digest return accurate quantiles as long as there is no information loss due to the merge of several centroids together.