Skip to content
Optimal Quantile Approximation in Streams
Go
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.circleci
demo
.gitignore
LICENSE
README.md
buffer.go
buffer_test.go
go.mod
go.sum
sketch.go
sketch_test.go
stream_example_test.go
summary.go
summary_test.go
utils.go

README.md

quantiles - Optimal Quantile Approximation in Streams

GoDoc CircleCI

This is a translation of TensorFlow's quantile helper class, it aims to compute approximate quantiles with error bound guarantees for weighted data sets. This implementation is an adaptation of techniques from the following papers:

The key ideas at play are the following:

  • Maintain an in-memory multi-level quantile summary in a way to guarantee a maximum approximation error of eps * W per bucket where W is the total weight across all points in the input dataset.
  • Two base operations are defined: MERGE and COMPRESS. MERGE combines two summaries guaranteeing a epsNew = max(eps1, eps2). COMPRESS compresses a summary to b + 1 elements guaranteeing epsNew = epsOld + 1/b.
  • b * sizeof(summary entry) must ideally be small enough to fit in an average CPU L2 cache.
  • To distribute this algorithm with maintaining error bounds, we need the worker-computed summaries to have no more than eps / h error where h is the height of the distributed computation graph which is 2 for an MR with no combiner.

We mainly want to max out IO bw by ensuring we're not compute-bound and using a reasonable amount of RAM.

Complexity:

  • Compute: O(n * log(1/eps * log(eps * n))).
  • Memory: O(1/eps * log^2(eps * n)) <- for one worker streaming through the entire dataset.

An epsilon value of zero would make the algorithm extremely inefficent and therefore, is disallowed.

Example Usage

package quantiles_test

import (
	"fmt"

	"github.com/axiomhq/quantiles"
)

func Example() {
	sketch := quantiles.NewDefault()
	for i := 0.0; i < 1e6; i++ {
		if err := sketch.Push(i, 1.0); err != nil {
			panic(err)
		}
	}
	fmt.Print("ApproximationError:") 	
	fmt.Println(sketch.ApproximationError(1))  // 0 <nil>

	fmt.Print("Finalize:") 
	fmt.Println(sketch.Finalize())            // <nil>

 
	fmt.Print("GenerateQuantiles(4):")         
	fmt.Println(sketch.GenerateQuantiles(4))  // [0 251865 503730 746595 999999] <nil>


	fmt.Print("GenerateQuantiles(10):")
	fmt.Println(sketch.GenerateQuantiles(10)) // [0 98946 197892 296838 395789 503730 602676 701622 800568 899514 999999] <nil>

	sum, err := sketch.FinalSummary()
	if err != nil {
		panic(err)
	}
	fmt.Print("GenerateQuantiles(4):")
	fmt.Println(sum.GenerateQuantiles(4))     // [0 251865 503730 746595 999999]
}

TODO

  • Implement an online estimator without the need of finalizing the stream
  • Add proper documentation
  • Benchmark
  • Add serialization
You can’t perform that action at this time.