tdigest

Documentation

Overview

Package tdigest provides an implementation of Ted Dunning's t-digest, an approximate histogram for online, distributed applications. For more details, refer to Dunning's paper and the reference implementations.

https://github.com/tdunning/t-digest/blob/master/docs/t-digest-paper/histo.pdf

https://github.com/tdunning/t-digest/blob/master/src/main/java/com/tdunning/math/stats/

Index

• type Centroid
• type MergingDigest
  • func NewMerging(compression float64, debug bool) *MergingDigest
  • func (td *MergingDigest) Add(value float64, weight float64)
  • func (td *MergingDigest) CDF(value float64) float64
  • func (td *MergingDigest) Centroids() []Centroid
  • func (td *MergingDigest) Count() float64
  • func (td *MergingDigest) GobDecode(b []byte) error
  • func (td *MergingDigest) GobEncode() ([]byte, error)
  • func (td *MergingDigest) Max() float64
  • func (td *MergingDigest) Merge(other *MergingDigest)
  • func (td *MergingDigest) Min() float64
  • func (td *MergingDigest) Quantile(quantile float64) float64

Types

type Centroid

type Centroid struct {
	Mean    float64
	Weight  float64
	Samples []float64
}

fields must be exported to allow encoding

type MergingDigest

type MergingDigest struct {
	// contains filtered or unexported fields
}

A t-digest using the merging implementation. MergingDigest is not safe for use by multiple goroutines simultaneously, and its methods must not be invoked concurrently (including Quantile and CDF).

func NewMerging

func NewMerging(compression float64, debug bool) *MergingDigest

Initializes a new merging t-digest using the given compression parameter. Lower compression values result in reduced memory consumption and less precision, especially at the median. Values from 20 to 1000 are recommended in Dunning's paper.

The debug flag adds a list to each centroid, which stores all the samples that have gone into that centroid. While this is useful for statistical analysis, it makes the t-digest significantly slower and requires it to store every sample. This defeats the purpose of using an approximating histogram at all, so this feature should only be used in tests.

func (*MergingDigest) Add

func (td *MergingDigest) Add(value float64, weight float64)

Adds a new value to the t-digest, with a given weight that must be positive. Infinities and NaN cannot be added.

func (*MergingDigest) CDF

func (td *MergingDigest) CDF(value float64) float64

Returns the approximate percentage of values in td that are below value (ie the cumulative distribution function). Returns NaN if the digest is empty.

func (*MergingDigest) Centroids

func (td *MergingDigest) Centroids() []Centroid

This function provides direct access to the internal list of centroids in this t-digest. Having access to this list is very important for analyzing the t-digest's statistical properties. However, since it violates the encapsulation of the t-digest, it should be used sparingly. Mutating the returned slice can result in undefined behavior.

This function will panic if debug is not enabled for this t-digest.

func (*MergingDigest) Count

func (td *MergingDigest) Count() float64

func (*MergingDigest) GobDecode

func (td *MergingDigest) GobDecode(b []byte) error

func (*MergingDigest) GobEncode

func (td *MergingDigest) GobEncode() ([]byte, error)

func (*MergingDigest) Max

func (td *MergingDigest) Max() float64

func (*MergingDigest) Merge

func (td *MergingDigest) Merge(other *MergingDigest)

Merge another digest into this one. Neither td nor other can be shared concurrently during the execution of this method.

func (*MergingDigest) Min

func (td *MergingDigest) Min() float64

func (*MergingDigest) Quantile

func (td *MergingDigest) Quantile(quantile float64) float64

Returns a value such that the fraction of values in td below that value is approximately equal to quantile. Returns NaN if the digest is empty.