DataDog/sketches-go

# sketches-go [](https://pkg.go.dev/github.com/DataDog/sketches-go/ddsketch) 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. ### Usage 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`. ## References [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 )

标签：EVTX分析