QTree
Related Docs:
class QTree
| package algebird
uses 1/65636 as the bin size, if you want to control that see other apply or value methods.
uses 1/65636 as the bin size, if you want to control that see other apply or value methods.
This is useful if you want to query the mean inside a range later. If you truly just care about the counts/histogram, see the value method.
The common case of wanting an offset and sum for the same value This is useful if you want to query the mean inside a range later.
The common case of wanting an offset and sum for the same value This is useful if you want to query the mean inside a range later. If you truly just care about the counts/histogram, see the value method.
level gives a bin size of 2^level. By default the bin size is 1/65536 (level = -16)
End user consumable unapply for QTree
If you are sure you only care about the approximate histogram features of QTree, you can save some space by using QTree[Unit] level gives a bin size of 2^level. By default this is 1/65536 (level = -16)
If you are sure you only care about the approximate histogram features of QTree, you can save some space by using QTree[Unit]
A QTree provides an approximate Map[Double,A:Monoid] suitable for range queries, quantile queries, and combinations of these (for example, if you use a numeric A, you can derive the inter-quartile mean).
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.
The basic idea is to keep a binary tree, where the root represents the entire range of the input keys, and each child node represents either the lower or upper half of its parent's range. Ranges are constrained to be dyadic intervals (https://en.wikipedia.org/wiki/Interval_(mathematics)#Dyadic_intervals) for ease of merging.
To keep the size bounded, the total count carried by any sub-tree must be at least 1/(2^k) of the total count at the root. Any sub-trees that do not meet this criteria have their children pruned and become leaves. (It's important that they not be pruned away entirely, but that we keep a fringe of low-count leaves that can gain weight over time and ultimately split again when warranted).
Quantile and range queries both give hard upper and lower bounds; the true result will be somewhere in the range given.
Keys must be >= 0.