tdunning/t-digest — pull request #31 by jpountz (2014-12-23 19:28:18+00:00)
Title: Add a new t-digest impl: BatchDigest.

This implementation is different from the ones we already have in the sense that
it does not try to always keep a sorted histogram. Instead it maintains a buffer
and a main histogram and periodically merges the buffer into the histogram.

Tests pass but I think it's still required to check this impl for correctness
given how different it is from the other impls (feedback is highly welcome!).

Although it would not be a good fit if you need to evalutate quantiles
periodically (every time that you do so, it needs to merge the buffer into the
main histogram), it seems to perform much faster (about 2x with a uniform
distribution, see output of the t-digest jmh benchmark below) for the 'batch'
case when you first add all your values and then evaluate quantiles.
![results](https://cloud.githubusercontent.com/assets/299848/5541926/3ba0aed8-8ae0-11e4-914e-d4912564ce42.png)

Another good property is that it is much less subject to worst-cases such as
sequential values, I got more than 10x speed-ups in those cases.