[vvern]

Aren't the goals of t-digest a little bit different?

T-digest seeks to have a bounded size and an error proportional to q*(1-q), hence it gives up quantile accuracy in the middle of the distribution when under load. This algorithm seems to provide total bounded error without small but unbounded size.

[tsenart]

Could you elaborate on the differences a bit deeper? I’m really interested in understanding.

[seiflotfy]

http://web.cs.ucla.edu/~weiwang/paper/SSDBM07_2.pdf is the paper its mostly based on Figure 1. Actually describes how big the datastructure can get. It keeps getting bigger the more data you feed it.