Package com.tdunning.math.stats
Class TreeDigest
java.lang.Object
com.tdunning.math.stats.TDigest
com.tdunning.math.stats.AbstractTDigest
com.tdunning.math.stats.TreeDigest
Adaptive histogram based on something like streaming k-means crossed with Q-digest.
The special characteristics of this algorithm are:
a) smaller summaries than Q-digest
b) works on doubles as well as integers.
c) provides part per million accuracy for extreme quantiles and typically <1000 ppm accuracy for middle quantiles
d) fast
e) simple
f) test coverage > 90%
g) easy to adapt for use with map-reduce
-
Field Summary
FieldsModifier and TypeFieldDescriptionstatic final int
static final int
Fields inherited from class com.tdunning.math.stats.AbstractTDigest
gen, recordAllData
-
Constructor Summary
ConstructorsConstructorDescriptionTreeDigest
(double compression) A histogram structure that will record a sketch of a distribution. -
Method Summary
Modifier and TypeMethodDescriptionvoid
add
(double x, int w) Adds a sample to a histogram.void
void
asBytes
(ByteBuffer buf) Outputs a histogram as bytes using a particularly cheesy encoding.void
asSmallBytes
(ByteBuffer buf) Serialize this TDigest into a byte buffer.int
byteSize()
Returns an upper bound on the number bytes that will be required to represent this histogram.double
cdf
(double x) Returns the fraction of all points added which are <= x.int
The number of centroids currently in the TDigest.An iterable that lets you go through the centroids in ascending order by mean.void
compress()
Re-examines a t-digest to determine whether some centroids are redundant.void
double
Returns the current compression factor.static TreeDigest
fromBytes
(ByteBuffer buf) Reads a histogram from a byte bufferstatic TDigest
double
quantile
(double q) Returns an estimate of the cutoff such that a specified fraction of the data added to this TDigest would be less than or equal to the cutoff.long
size()
Returns the number of samples represented in this histogram.int
Returns an upper bound on the number of bytes that will be required to represent this histogram in the tighter representation.Methods inherited from class com.tdunning.math.stats.AbstractTDigest
add, add, createCentroid, decode, encode, interpolate, isRecording, merge, recordAllData
Methods inherited from class com.tdunning.math.stats.TDigest
checkValue, createArrayDigest, createArrayDigest, createTreeDigest
-
Field Details
-
VERBOSE_ENCODING
public static final int VERBOSE_ENCODING- See Also:
-
SMALL_ENCODING
public static final int SMALL_ENCODING- See Also:
-
-
Constructor Details
-
TreeDigest
public TreeDigest(double compression) A histogram structure that will record a sketch of a distribution.- Parameters:
compression
- How should accuracy be traded for size? A value of N here will give quantile errors almost always less than 3/N with considerably smaller errors expected for extreme quantiles. Conversely, you should expect to track about 5 N centroids for this accuracy.
-
-
Method Details
-
add
public void add(double x, int w) Description copied from class:TDigest
Adds a sample to a histogram. -
add
-
merge
-
compress
public void compress()Description copied from class:TDigest
Re-examines a t-digest to determine whether some centroids are redundant. If your data are perversely ordered, this may be a good idea. Even if not, this may save 20% or so in space. The cost is roughly the same as adding as many data points as there are centroids. This is typically < 10 * compression, but could be as high as 100 * compression. This is a destructive operation that is not thread-safe. -
compress
- Specified by:
compress
in classAbstractTDigest
-
size
public long size()Returns the number of samples represented in this histogram. If you want to know how many centroids are being used, try centroids().size(). -
cdf
public double cdf(double x) Description copied from class:TDigest
Returns the fraction of all points added which are <= x. -
quantile
public double quantile(double q) Description copied from class:TDigest
Returns an estimate of the cutoff such that a specified fraction of the data added to this TDigest would be less than or equal to the cutoff. -
centroidCount
public int centroidCount()Description copied from class:TDigest
The number of centroids currently in the TDigest.- Specified by:
centroidCount
in classTDigest
- Returns:
- The number of centroids
-
centroids
Description copied from class:TDigest
An iterable that lets you go through the centroids in ascending order by mean. Centroids returned will not be re-used, but may or may not share storage with this TDigest. -
compression
public double compression()Description copied from class:TDigest
Returns the current compression factor.- Specified by:
compression
in classTDigest
- Returns:
- The compression factor originally used to set up the TDigest.
-
byteSize
public int byteSize()Returns an upper bound on the number bytes that will be required to represent this histogram. -
smallByteSize
public int smallByteSize()Returns an upper bound on the number of bytes that will be required to represent this histogram in the tighter representation.- Specified by:
smallByteSize
in classTDigest
- Returns:
- The number of bytes required.
-
asBytes
Outputs a histogram as bytes using a particularly cheesy encoding. -
asSmallBytes
Description copied from class:TDigest
Serialize this TDigest into a byte buffer. Some simple compression is used such as using variable byte representation to store the centroid weights and using delta-encoding on the centroid means so that floats can be reasonably used to store the centroid means.- Specified by:
asSmallBytes
in classTDigest
- Parameters:
buf
- The byte buffer into which the TDigest should be serialized.
-
fromBytes
Reads a histogram from a byte buffer- Returns:
- The new histogram structure
-