tdunning/t-digest — pull request #17 by jpountz (2014-03-20 00:35:53+00:00)
Title: Faster tree-based t-digest.

Improved tree-based t-digest, with the following changes compared to the
previous implementation:
- the array structure is stored in parallel arrays instead of a tree of
objects,
- data is stored both on inner nodes and leaf nodes,
- data is updated in-place when this would not trigger a reordering
of the tree (possible by tracking parents).

Simplistic benchmarks seem to suggest this is a faster than the current
ArrayDigest implementation.

I don't consider it ready yet: even if it passes the test suite, I need to spend
more time making sure it works correctly, but I'd be happy to have your feedback
about whether it is a good idea to work on the tree-based implementation
(I saw in a previous comment that you are considering deprecating the tree
digest, but if my understanding is correct, this is more because it currently stores
Centroids objects than because it is a tree?). The code might not be very easy to
digest so feel free to ask any questions!