Package com.tdunning.math.stats

# Class TDigest

java.lang.Object
com.tdunning.math.stats.TDigest

Direct Known Subclasses:
  `AbstractTDigest`

public abstract class TDigest extends Object
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 invalid input: '<'1000 ppm accuracy for middle quantiles

d) fast

e) simple

f) test coverage > 90%

g) easy to adapt for use with map-reduce

## Constructor Summary

Constructors
Constructor
Description
`TDigest()`

## Method Summary

Modifier and Type
Method
Description
`abstract void`
`add(double x)`
Add a sample to this TDigest.
`abstract void`
`add(double x, int w)`
Adds a sample to a histogram.
`abstract void`
`add(TDigest other)`
Add all of the centroids of another TDigest to this one.
`abstract void`
`asBytes(ByteBuffer buf)`
Serialize this TDigest into a byte buffer.
`abstract void`
`asSmallBytes(ByteBuffer buf)`
Serialize this TDigest into a byte buffer.
`abstract int`
`byteSize()`
Returns the number of bytes required to encode this TDigest using #asBytes().
`abstract double`
`cdf(double x)`
Returns the fraction of all points added which are invalid input: '<'= x.
`abstract int`
`centroidCount()`
The number of centroids currently in the TDigest.
`abstract Iterable<? extends Centroid>`
`centroids()`
An iterable that lets you go through the centroids in ascending order by mean.
`protected final void`
`checkValue(double x)`
`abstract void`
`compress()`
Re-examines a t-digest to determine whether some centroids are redundant.
`abstract double`
`compression()`
Returns the current compression factor.
`static ArrayDigest`
`createArrayDigest(double compression)`
Creates an ArrayDigest with default page size.
`static ArrayDigest`
`createArrayDigest(int pageSize, double compression)`
Creates an ArrayDigest with specified page size.
`static TDigest`
`createTreeDigest(double compression)`
Creates a TreeDigest.
`abstract boolean`
`isRecording()`
`abstract 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.
`abstract TDigest`
`recordAllData()`
Tell this TDigest to record the original data as much as possible for test purposes.
`abstract long`
`size()`
Returns the number of points that have been added to this TDigest.
`abstract int`
`smallByteSize()`
Returns the number of bytes required to encode this TDigest using #asSmallBytes().

### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

## Constructor Details

### TDigest

public TDigest()

## Method Details

### createArrayDigest

public static ArrayDigest createArrayDigest(double compression)
Creates an ArrayDigest with default page size.

Parameters:
  `compression` - The compression parameter. 100 is a common value for normal uses. 1000 is extremely large. The number of centroids retained will be a smallish (usually less than 10) multiple of this number.
Returns:
  the ArrayDigest

### createArrayDigest

public static ArrayDigest createArrayDigest(int pageSize, double compression)
Creates an ArrayDigest with specified page size.

Parameters:
  `pageSize` - The internal page size to use. This should be about sqrt(10*compression)
  `compression` - The compression parameter. 100 is a common value for normal uses. 1000 is extremely large. The number of centroids retained will be a smallish (usually less than 10) multiple of this number.
Returns:
  the ArrayDigest

### createTreeDigest

public static TDigest createTreeDigest(double compression)
Creates a TreeDigest. Going forward, ArrayDigests should be preferred to the TreeDigest since they are uniformly faster and require less memory while producing nearly identical results.

Parameters:
  `compression` - The compression parameter. 100 is a common value for normal uses. 1000 is extremely large. The number of centroids retained will be a smallish (usually less than 10) multiple of this number.
Returns:
  the TreeDigest

### add

public abstract void add(double x, int w)
Adds a sample to a histogram.

Parameters:
  `x` - The value to add.
  `w` - The weight of this point.

### checkValue

protected final void checkValue(double x)

### compress

public abstract void compress()
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 invalid input: '<' 10 * compression, but could be as high as 100 * compression.

This is a destructive operation that is not thread-safe.

### size

public abstract long size()
Returns the number of points that have been added to this TDigest.

Returns:
  The sum of the weights on all centroids.

### cdf

public abstract double cdf(double x)
Returns the fraction of all points added which are invalid input: '<'= x.

### quantile

public abstract 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.

Parameters:
  `q` - The desired fraction
Returns:
  The value x such that cdf(x) == q

### centroidCount

public abstract int centroidCount()
The number of centroids currently in the TDigest.

Returns:
  The number of centroids

### centroids

public abstract Iterable<? extends Centroid> centroids()
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.

Returns:
  The centroids in the form of an Iterable.

### compression

public abstract double compression()
Returns the current compression factor.

Returns:
  The compression factor originally used to set up the TDigest.

### byteSize

public abstract int byteSize()
Returns the number of bytes required to encode this TDigest using #asBytes().

Returns:
  The number of bytes required.

### smallByteSize

public abstract int smallByteSize()
Returns the number of bytes required to encode this TDigest using #asSmallBytes().

Returns:
  The number of bytes required.

### asBytes

public abstract void asBytes(ByteBuffer buf)
Serialize this TDigest into a byte buffer. Note that the serialization used is very straightforward and is considerably larger than strictly necessary.

Parameters:
  `buf` - The byte buffer into which the TDigest should be serialized.

### asSmallBytes

public abstract void asSmallBytes(ByteBuffer buf)
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.

Parameters:
  `buf` - The byte buffer into which the TDigest should be serialized.

### recordAllData

public abstract TDigest recordAllData()
Tell this TDigest to record the original data as much as possible for test purposes.

Returns:
  This TDigest so that configurations can be done in fluent style.

### isRecording

public abstract boolean isRecording()

### add

public abstract void add(double x)
Add a sample to this TDigest.

Parameters:
  `x` - The data value to add

### add

public abstract void add(TDigest other)
Add all of the centroids of another TDigest to this one.

Parameters:
  `other` - The other TDigest