gk

README

Optimized Greenwald-Khanna streaming quantiles.

On my laptop, this processes numbers at a rate of 1.2 seconds per million numbers.

Godoc: http://godoc.org/github.com/dgryski/go-gk

Documentation

Overview

Package gk implmements Greenwald/Khanna's streaming quantiles

"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

• type Exact
  • func NewExact() *Exact
  • func (ex *Exact) Insert(v float64)
  • func (ex *Exact) Query(q float64) float64
• type Stream
  • func New(epsilon float64) *Stream
  • func (s *Stream) Insert(v float64)
  • func (s *Stream) Query(q float64) float64

Types

type Exact

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

Exact is an exact (map-based) quantile summary

func NewExact

func NewExact() *Exact

NewExact returns a new exact quantile summary

func (*Exact) Insert

func (ex *Exact) Insert(v float64)

Insert inserts an item into the quantile summary

func (*Exact) Query

func (ex *Exact) Query(q float64) float64

Query returns the qth quantile of the stream

type Stream

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

Stream is a quantile summary

func New

func New(epsilon float64) *Stream

New returns a new stream with accuracy epsilon (0 <= epsilon <= 1)

func (*Stream) Insert

func (s *Stream) Insert(v float64)

Insert inserts an item into the quantile summary

func (*Stream) Query

func (s *Stream) Query(q float64) float64

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