README
¶
Exponential histograms 
Exponential histograms is a data structure for sliding windows. It is from Maintaining Stream Statistics over Sliding Windows, M.Datar, A.Gionis, P.Indyk, R.Motwani; ACM-SIAM, 2002.
See also
- https://www.dbs.ifi.lmu.de/Lehre/BigData-Management&Analytics/WS15-16/Chapter-5_Stream_Processing_part2.pdf
- http://www.facom.ufu.br/~elaine/disc/MFCD/histograms.pdf
Usage
Exponential histograms requires windowSize and epsilon for parameter. The epsilon controls timing of merging the oldest two buckets into one bucket double the size.
Exponential histograms estimates count value in the window. The absolute error in the value is at most C/2, where C is the size of the last bucket.
Bits
hist := New(10, 0.5)
stream := []uint{1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0}
for _, x := range stream {
hist.Add(x)
}
count := hist.Count()
fmt.Println(count) // 6.0 (Actual: 8.0)
Positive integers
hist := New(200, 0.01)
for i := 1; i <= 200; i++ {
hist.Add(uint(i))
}
count := hist.Count()
fmt.Println(count) // 19972.0 (Actual: 20100.0)
Real numbers
hist := NewForRealNumber(2)
for i := 1; i <= 200; i++ {
hist.Add(float64(i))
}
sum := hist.Sum()
fmt.Println(sum) // 20100.0 (Actual: 20100.0)
size := hist.Size()
fmt.Println(size) // 200.0
Vector of real numbers (Original)
hist := NewForVector(2)
for i := 1; i <= 200; i++ {
hist.Add([]float64{float64(i), float64(i)})
}
sum := hist.Sum()
fmt.Println(sum) // [20100.0 20100.0] (Actual: [20100.0 20100.0])
size := hist.Size()
fmt.Println(size) // 200.0
Installation
$ go get github.com/monochromegane/exponential-histograms
License
Author
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type ExpHistRealNumber ¶
type ExpHistRealNumber struct {
// contains filtered or unexported fields
}
func NewForRealNumber ¶
func NewForRealNumber(m int) *ExpHistRealNumber
func (*ExpHistRealNumber) Add ¶
func (e *ExpHistRealNumber) Add(x float64)
func (*ExpHistRealNumber) Drop ¶
func (e *ExpHistRealNumber) Drop()
func (*ExpHistRealNumber) Scale ¶
func (e *ExpHistRealNumber) Scale(gamma float64)
func (*ExpHistRealNumber) Size ¶
func (e *ExpHistRealNumber) Size() int
func (*ExpHistRealNumber) Sum ¶
func (e *ExpHistRealNumber) Sum() float64
func (*ExpHistRealNumber) Tail ¶
func (e *ExpHistRealNumber) Tail() Buckets
type ExpHistVector ¶
type ExpHistVector struct {
// contains filtered or unexported fields
}
func NewForVector ¶
func NewForVector(m int) *ExpHistVector
func (*ExpHistVector) Add ¶
func (e *ExpHistVector) Add(x []float64)
func (*ExpHistVector) Drop ¶
func (e *ExpHistVector) Drop()
func (*ExpHistVector) Scale ¶
func (e *ExpHistVector) Scale(gamma float64)
func (*ExpHistVector) Size ¶
func (e *ExpHistVector) Size() int
func (*ExpHistVector) Sum ¶
func (e *ExpHistVector) Sum() []float64
func (*ExpHistVector) Tail ¶
func (e *ExpHistVector) Tail() VectorBuckets
type VectorBucket ¶
type VectorBucket struct {
// contains filtered or unexported fields
}
type VectorBuckets ¶
type VectorBuckets [][]VectorBucket
func (VectorBuckets) Size ¶
func (b VectorBuckets) Size() int
func (VectorBuckets) Sum ¶
func (b VectorBuckets) Sum() []float64
Source Files
Click to show internal directories.
Click to hide internal directories.