twitter/algebird — pull request #159 by avibryant (2013-04-27 05:54:57+00:00)
Title: QTree

A QTree provides an approximate Map[Double,A:Semigroup] suitable for range queries, quantile queries, and combinations of these.

It is loosely related to the Q-Digest data structure from http://www.cs.virginia.edu/~son/cs851/papers/ucsb.sensys04.pdf, but using an immutable tree structure, and carrying a generalized sum (of type A) at each node instead of just a count.

Addresses issue #158.