t-digestというデータ構造
This content is a draft and will not be included in production builds.
t-digestとは、PercentileやQuantileなど分位数の近似値を比較的小さいメモリで表現するためのデータ構造と、それとペアになるアルゴリズムの名称。
ひとつの値は Centroid という単位で表現しており、これは重みと値を持つ。
struct Centroid { double weight; /* 値の重み */ double mean; /* 値 */};ライブラリに寄るかもしれないが、npm パッケージの tdigest では、重みはだいたい個数に近い値となっていて、例えば100という値が20個あれば、weight が20で mean が100の Centroid ひとつで表される。当然こんなにきれいな圧縮は起きないので、その場合は重みと値で近似値を表現する。
ひとつの Centroid がどれだけの質量(含有する元データの数)を持てるかについては、tdigest パッケージの場合は圧縮率で設定可能となっていて、この値を1.0(最大)にするとひとつの Centroid で近似値を表現する意味となり、0.5にすると2つの Centroid で近似値をする、となる。デフォルトは0.01なのでだいたい100個の Centroid が用いられる。
Redisにはt-digestを扱うコマンドがある。