veneur: github.com/stripe/veneur/tdigest Index | Files | Directories

package tdigest

import "github.com/stripe/veneur/tdigest"

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

Package Files

merging_digest.go tdigest.pb.go

Variables

var (
    ErrInvalidLengthTdigest = fmt.Errorf("proto: negative length found during unmarshaling")
    ErrIntOverflowTdigest   = fmt.Errorf("proto: integer overflow")
)

type Centroid Uses

type Centroid struct {
    Mean    float64   `protobuf:"fixed64,1,opt,name=mean,proto3" json:"mean,omitempty"`
    Weight  float64   `protobuf:"fixed64,2,opt,name=weight,proto3" json:"weight,omitempty"`
    Samples []float64 `protobuf:"fixed64,3,rep,packed,name=samples,proto3" json:"samples,omitempty"`
}

func (*Centroid) Descriptor Uses

func (*Centroid) Descriptor() ([]byte, []int)

func (*Centroid) GetMean Uses

func (m *Centroid) GetMean() float64

func (*Centroid) GetSamples Uses

func (m *Centroid) GetSamples() []float64

func (*Centroid) GetWeight Uses

func (m *Centroid) GetWeight() float64

func (*Centroid) Marshal Uses

func (m *Centroid) Marshal() (dAtA []byte, err error)

func (*Centroid) MarshalTo Uses

func (m *Centroid) MarshalTo(dAtA []byte) (int, error)

func (*Centroid) ProtoMessage Uses

func (*Centroid) ProtoMessage()

func (*Centroid) Reset Uses

func (m *Centroid) Reset()

func (*Centroid) Size Uses

func (m *Centroid) Size() (n int)

func (*Centroid) String Uses

func (m *Centroid) String() string

func (*Centroid) Unmarshal Uses

func (m *Centroid) Unmarshal(dAtA []byte) error

func (*Centroid) XXX_DiscardUnknown Uses

func (m *Centroid) XXX_DiscardUnknown()

func (*Centroid) XXX_Marshal Uses

func (m *Centroid) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*Centroid) XXX_Merge Uses

func (m *Centroid) XXX_Merge(src proto.Message)

func (*Centroid) XXX_Size Uses

func (m *Centroid) XXX_Size() int

func (*Centroid) XXX_Unmarshal Uses

func (m *Centroid) XXX_Unmarshal(b []byte) error

type MergingDigest Uses

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 Uses

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 NewMergingFromData Uses

func NewMergingFromData(d *MergingDigestData) *MergingDigest

NewMergingFromData returns a MergingDigest with values initialized from MergingDigestData. This should be the way to generate a MergingDigest from a serialized protobuf.

func (*MergingDigest) Add Uses

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 Uses

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 Uses

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 Uses

func (td *MergingDigest) Count() float64

func (*MergingDigest) Data Uses

func (td *MergingDigest) Data() *MergingDigestData

Data returns a MergingDigestData based on the MergingDigest (which contains just a subset of the fields). This can be used with proto.Marshal to encode a MergingDigest as a protobuf.

func (*MergingDigest) GobDecode Uses

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

func (*MergingDigest) GobEncode Uses

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

func (*MergingDigest) Max Uses

func (td *MergingDigest) Max() float64

func (*MergingDigest) Merge Uses

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 Uses

func (td *MergingDigest) Min() float64

func (*MergingDigest) Quantile Uses

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.

func (*MergingDigest) ReciprocalSum Uses

func (td *MergingDigest) ReciprocalSum() float64

func (*MergingDigest) Sum Uses

func (td *MergingDigest) Sum() float64

type MergingDigestData Uses

type MergingDigestData struct {
    // Use values rather than pointers for the Centroid array.  This avoids
    // a ton of code changes and probably a lot of allocations as well.
    MainCentroids []Centroid `protobuf:"bytes,1,rep,name=main_centroids,json=mainCentroids,proto3" json:"main_centroids"`
    Compression   float64    `protobuf:"fixed64,2,opt,name=compression,proto3" json:"compression,omitempty"`
    Min           float64    `protobuf:"fixed64,3,opt,name=min,proto3" json:"min,omitempty"`
    Max           float64    `protobuf:"fixed64,4,opt,name=max,proto3" json:"max,omitempty"`
    ReciprocalSum float64    `protobuf:"fixed64,5,opt,name=reciprocalSum,proto3" json:"reciprocalSum,omitempty"`
}

MergingDigestData contains all fields necessary to generate a MergingDigest. This type should generally just be used when serializing MergingDigest's, and doesn't have much of a purpose on its own.

func (*MergingDigestData) Descriptor Uses

func (*MergingDigestData) Descriptor() ([]byte, []int)

func (*MergingDigestData) GetCompression Uses

func (m *MergingDigestData) GetCompression() float64

func (*MergingDigestData) GetMainCentroids Uses

func (m *MergingDigestData) GetMainCentroids() []Centroid

func (*MergingDigestData) GetMax Uses

func (m *MergingDigestData) GetMax() float64

func (*MergingDigestData) GetMin Uses

func (m *MergingDigestData) GetMin() float64

func (*MergingDigestData) GetReciprocalSum Uses

func (m *MergingDigestData) GetReciprocalSum() float64

func (*MergingDigestData) Marshal Uses

func (m *MergingDigestData) Marshal() (dAtA []byte, err error)

func (*MergingDigestData) MarshalTo Uses

func (m *MergingDigestData) MarshalTo(dAtA []byte) (int, error)

func (*MergingDigestData) ProtoMessage Uses

func (*MergingDigestData) ProtoMessage()

func (*MergingDigestData) Reset Uses

func (m *MergingDigestData) Reset()

func (*MergingDigestData) Size Uses

func (m *MergingDigestData) Size() (n int)

func (*MergingDigestData) String Uses

func (m *MergingDigestData) String() string

func (*MergingDigestData) Unmarshal Uses

func (m *MergingDigestData) Unmarshal(dAtA []byte) error

func (*MergingDigestData) XXX_DiscardUnknown Uses

func (m *MergingDigestData) XXX_DiscardUnknown()

func (*MergingDigestData) XXX_Marshal Uses

func (m *MergingDigestData) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*MergingDigestData) XXX_Merge Uses

func (m *MergingDigestData) XXX_Merge(src proto.Message)

func (*MergingDigestData) XXX_Size Uses

func (m *MergingDigestData) XXX_Size() int

func (*MergingDigestData) XXX_Unmarshal Uses

func (m *MergingDigestData) XXX_Unmarshal(b []byte) error

Directories

PathSynopsis
analysis

Package tdigest imports 11 packages (graph) and is imported by 16 packages. Updated 2019-06-14. Refresh now. Tools for package owners.