Implement tdigest

[tisonkun]

Ref -

• https://github.com/apache/datasketches-cpp/tree/master/tdigest
• https://github.com/apache/datasketches-java/tree/main/src/main/java/org/apache/datasketches/tdigest
• https://apache.github.io/datasketches-python/5.2.0/quantiles/tdigest.html
• https://apache.github.io/datasketches-java/9.0.0/org/apache/datasketches/tdigest/package-summary.html

Previously, @andylokandy developed https://github.com/andylokandy/tdigests/, and we are using it in production for use cases like approx_quantile. I hope we can reuse the kernel code, but it should follow the datasketches API flavor and serialization format.

[tisonkun]

Perhaps we can have DDSketch into this repo as well and test whether tdigest or ddsketch the better in concrete scenarios.

cc @notfilippo @freakyzoidberg I remember you guys are working at DataDog and there is an ALv2 licensed https://github.com/DataDog/sketches-java. Any plan to have it in Apache DataSketches and/or have a Rust impl?

[notfilippo]

There is a PR in datasketches-cpp to introduce DDSketch. Personally, would be open to the idea.

cc @geonove

[geonove]

Yes, I am currently working on a study to compare t-digest, req sketch and ddsketch (from the cpp implementations). I can give updates on this thread as well as soon as I have some meaningful results