This repo contains Go implementations of the distributed quantile sketch algorithm
DDSketch [1]. DDSketch has relative-error guarantees for any quantile q in [0, 1].
That is if the true value of the qth-quantile is x
then DDSketch returns a value y
such that |x-y| / x < e
where e
is the relative error parameter. DDSketch is also
fully mergeable, meaning that multiple sketches from distributed systems can be combined
in a central node.
Our default implementation, returned from NewDefaultDDSketch(relativeAccuracy)
, is
guaranteed [1] not to grow too large in size for any data that can be described by a
distribution whose tails are sub-exponential.
We also provide implementations, returned by LogCollapsingLowestDenseDDSketch(relativeAccuracy, maxNumBins)
and LogCollapsingHighestDenseDDSketch(relativeAccuracy, maxNumBins)
, where the q-quantile
will be accurate up to the specified relative error for q that is not too small (or large).
Concretely, the q-quantile will be accurate up to the specified relative error as long as it
belongs to one of the m
bins kept by the sketch. For instance, If the values are time in seconds,
maxNumBins = 2048
covers a time range from 80 microseconds to 1 year.
import "github.com/DataDog/sketches-go/ddsketch"
relativeAccuracy := 0.01
sketch := ddsketch.NewDefaultDDSketch(relativeAccuracy)
Add values to the sketch.
import "math/rand"
for i := 0; i < 500; i {
v := rand.NormFloat64()
sketch.Add(v)
}
Find the quantiles to within alpha relative error.
qs := []float64{0.5, 0.75, 0.9, 1}
quantiles, err := sketch.GetValuesAtQuantiles(qs)
Merge another DDSketch
into sketch
.
anotherSketch := ddsketch.NewDefaultDDSketch(relativeAccuracy)
for i := 0; i < 500; i {
v := rand.NormFloat64()
anotherSketch.Add(v)
}
sketch.MergeWith(anotherSketch)
The quantiles are in sketch
are still accurate to within relativeAccuracy
.
[1] Charles Masson and Jee E Rim and Homin K. Lee. DDSketch: A fast and fully-mergeable quantile sketch with relative-error guarantees. PVLDB, 12(12): 2195-2205, 2019. (The code referenced in the paper, including our implementation of the the Greenwald-Khanna (GK) algorithm, can be found at: https://github.com/DataDog/sketches-go/releases/tag/v0.0.1 )