tdunning/t-digest — pull request #18 by jpountz (2014-04-18 20:55:05+00:00)
Title: Faster quantile estimations.

Quantile estimation is currently linear with the number of centroids. However
it is possible to compute quantiles in logarithmic time by using the aggregated
counts that are stored on each node and running a binary search.

The quantile estimation method has also been improved in order to not
materialize objects anymore.

It doesn't matter much if you use t-digest with a batch approach and first
accumulate all values before computing quantiles in a final step. But this
speedup means that it is now possible to interleave accumulation and quantile
estimation without killing performance.