quantile

README

Sketches

Papers:

• GK Quantiles
• An Experimental Study of Distributed Quantile Estimation
• Mergeable Summaries
• Almost Optimal Streaming Quantiles Algorithms
• A Streaming Parallel Decision Tree Algorithm

Blogs:

• Streaming Approximate Histograms in Go

Documentation

Overview

Package quantile implements "Space-Efficient Online Computation of Quantile Summaries" (Greenwald, Khanna 2001): http://infolab.stanford.edu/~datar/courses/cs361a/papers/quantiles.pdf

This implementation is backed by a skiplist to make inserting elements into the summary faster. Querying is still O(n).

Index

• Constants
• type Entry
• type SliceSummary
  • func NewSliceSummary() *SliceSummary
  • func WeighSummary(s *SliceSummary, weight float64) *SliceSummary
  • func (s *SliceSummary) BySlices() []SummarySlice
  • func (s *SliceSummary) Copy() *SliceSummary
  • func (s *SliceSummary) Insert(v float64, t uint64)
  • func (s *SliceSummary) Merge(s2 *SliceSummary)
  • func (s *SliceSummary) Quantile(q float64) float64
  • func (s SliceSummary) String() string
• type SummarySlice
  • func BySlicesWeighted(summaries ...WeightedSliceSummary) []SummarySlice
• type WeightedSliceSummary

Constants

const EPSILON float64 = 0.01

EPSILON is the precision of the rank returned by our quantile queries

Types

type Entry

type Entry struct {
	V     float64 `json:"v"`
	G     int     `json:"g"`
	Delta int     `json:"delta"`
}

Entry is an element of the skiplist, see GK paper for description

type SliceSummary

type SliceSummary struct {
	Entries []Entry
	N       int
}

SliceSummary is a GK-summary with a slice backend

func NewSliceSummary

func NewSliceSummary() *SliceSummary

NewSliceSummary allocates a new GK summary backed by a DLL

func WeighSummary

func WeighSummary(s *SliceSummary, weight float64) *SliceSummary

WeighSummary applies a weight factor to a slice summary and return it as a new slice.

func (*SliceSummary) BySlices

func (s *SliceSummary) BySlices() []SummarySlice

BySlices returns a slice of Summary slices that represents weighted ranges of values e.g. [0, 1] : 3

[1, 23] : 12 ...

The number of intervals is related to the precision kept in the internal data structure to ensure epsilon*s.N precision on quantiles, but it's bounded. When the bounds of the interval are equal, the weight is the number of times that exact value was inserted in the summary.

func (*SliceSummary) Copy

func (s *SliceSummary) Copy() *SliceSummary

Copy allocates a new summary with the same data

func (*SliceSummary) Insert

func (s *SliceSummary) Insert(v float64, t uint64)

Insert inserts a new value v in the summary paired with t (the ID of the span it was reported from)

func (*SliceSummary) Merge

func (s *SliceSummary) Merge(s2 *SliceSummary)

Merge two summaries entries together

func (*SliceSummary) Quantile

func (s *SliceSummary) Quantile(q float64) float64

Quantile returns an EPSILON estimate of the element at quantile 'q' (0 <= q <= 1)

func (SliceSummary) String

func (s SliceSummary) String() string

type SummarySlice

type SummarySlice struct {
	Start  float64
	End    float64
	Weight int
}

SummarySlice reprensents how many values are in a [Start, End] range

func BySlicesWeighted

func BySlicesWeighted(summaries ...WeightedSliceSummary) []SummarySlice

BySlicesWeighted BySlices() is the BySlices version but combines multiple weighted slice summaries before returning the histogram

type WeightedSliceSummary

type WeightedSliceSummary struct {
	Weight float64
	*SliceSummary
}

WeightedSliceSummary associates a weight to a slice summary.