README
¶
Streaming Quantile Estimator
Implements ideas found in Effective Computation of Biased Quantiles over Data Streams (Cormode, Korn, Muthukrishnan, Srivastava) to provide a space and time efficient estimator for streaming quantile estimation.
Documentation
¶
Overview ¶
Package quantile implements a streaming quantile estimator. The implementation is based on "Effective Computation of Biased Quantiles over Data Streams" (Cormode, Korn, Muthukrishnan, Srivastava) to provide a space and time efficient estimator for online quantile estimation.
For the normal distribution of 10^9 elements, a tolerance for 0.99th percentile at 0.001 uses under 1000 bins at 32 bytes per bin.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Estimate ¶
type Estimate interface {
// Delta calculates the acceptable difference in ranks between two values.
// It is used to remove redundant values during compression.
Delta(rank, observations float64) float64
}
func Known ¶
Known produces a optimal space usage for estimations at the given quantile and error tolerance.
Quantiles not known ahead of time can also be queried, but at a lower accuracy.
type Estimator ¶
type Estimator struct {
// contains filtered or unexported fields
}
func New ¶
New allocates a new estimator tolerating the minimum of the invariants provided.
When you know how much error you can tolerate in the quantiles you will query, use a Known estimation for each quantile you will query. For example:
quantile.New(quantile.Known(0.50, 0.01), quantile.Known(0.95, 0.001), quantile.Known(0.99, 0.0005))
When you will query for multiple different quantiles, and know the error tolerance, use the Bias invariant. For example:
quantile.New(quantile.Unknown(0.01))
Targeted estimators consume significantly less resources than Biased estimators.
Passing no parameters will create an estimator that has a tolerance of 0.1, equivalent to:
quantile.New(quantile.Unknown(0.1))
Estimators are not safe to use from multiple goroutines.
func (*Estimator) Add ¶
Add buffers a new sample, committing and compressing the data structure when the buffer is full.
Source Files