5 ms·
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 acc
by vvern 8y ago
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 8y agoCould you elaborate on the differences a bit deeper? I’m really interested in understanding.
- seiflotfy 8y agohttp://web.cs.ucla.edu/~weiwang/paper/SSDBM07_2.pdf 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.