Skip to content
A T-Digest implementation in golang
Branch: master
Clone or download
caio Drop everything TravisCI
I won't trust the new owner with access to my account.

Also: https://twitter.com/carmatrocity/status/1098538649908666368
Latest commit 1b37924 Feb 22, 2019
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.gitignore Add a basic .gitignore Oct 30, 2017
CONTRIBUTING.md Drop everything TravisCI Feb 22, 2019
Gopkg.lock Change fenwick tree to accept uint32 to avoid extra copy Nov 4, 2018
Gopkg.toml Change fenwick tree to accept uint32 to avoid extra copy Nov 4, 2018
LICENSE Add license Aug 23, 2015
README.md
options.go Tidy things up [gometalinter] Oct 30, 2017
options_test.go Add TDigest.FromBytes and cleanup RNG interface Nov 10, 2018
rng.go Add TDigest.FromBytes and cleanup RNG interface Nov 10, 2018
serialization.go Make FromBytes accept options for constructing the digest Nov 13, 2018
serialization_test.go Make FromBytes accept options for constructing the digest Nov 13, 2018
summary.go Add TDigest.FromBytes and cleanup RNG interface Nov 10, 2018
summary_test.go Use rand.Perm to shuffle data Nov 8, 2018
tdigest.go Make FromBytes accept options for constructing the digest Nov 13, 2018
tdigest_test.go Use uncheckedNew() Nov 13, 2018

README.md

T-Digest

A fast map-reduce and parallel streaming friendly data-structure for accurate quantile approximation.

This package provides an implementation of Ted Dunning's t-digest data structure in Go.

GoDoc Go Report Card

Project Status

This project is actively maintained. We are happy to collaborate on features and issues if/when they arrive.

Installation

Our releases are tagged and signed following the Semantic Versioning scheme. If you are using a dependency manager such as dep, the recommended way to is go about your business normally:

go get github.com/caio/go-tdigest

Otherwise we recommend to use the following so that you don't risk breaking your build because of an API change:

go get gopkg.in/caio/go-tdigest.v2

Example Usage

package main

import (
	"fmt"
	"math/rand"

	"github.com/caio/go-tdigest"
)

func main() {
	// Analogue to tdigest.New(tdigest.Compression(100))
	t, _ := tdigest.New()

	for i := 0; i < 10000; i++ {
		// Analogue to t.AddWeighted(rand.Float64(), 1)
		t.Add(rand.Float64())
	}

	fmt.Printf("p(.5) = %.6f\n", t.Quantile(0.5))
	fmt.Printf("CDF(Quantile(.5)) = %.6f\n", t.CDF(t.Quantile(0.5)))
}

Configuration

You can configure your digest upon creation with options documented at options.go. Example:

// Construct a digest with compression=200 and its own
// (thread-unsafe) RNG seeded with 0xCA10:
digest, _ := tdigest.New(
        tdigest.Compression(200),
        tdigest.LocalRandomNumberGenerator(0xCA10),
)

Porting Existing Code to the v2 API

It's very easy to migrate to the new API:

  • Replace tdigest.New(100) with tdigest.New()
  • Replace tdigest.New(number) with tdigest.New(tdigest.Compression(number))
  • Replace Add(x,1) with Add(x)
  • Replace Add(x, weight) with AddWeighted(x, weight)
  • Remove any use of tdigest.Len() (or open an issue)

References

This is a port of the reference implementation with some ideas borrowed from the python version. If you wanna get a quick grasp of how it works and why it's useful, this video and companion article is pretty helpful.

You can’t perform that action at this time.