Skip to content

A concurrent, go(lang) implemention the t-digest streaming quantile estimation data structure.

License

Notifications You must be signed in to change notification settings

ajwerner/tdigest

Repository files navigation

tdigest

Documentation

This is a concurrent go implementation of the t-digest data structure for streaming quantile estimation. The code implements the zero-allocation, merging algorithm from Ted Dunning's paper (here).

It utilizes the later iteration of the scale functions, currently just exposing scale function k_2 from the paper.

The implementation strives to make concurrent writes cheap. In the common case a write needs only increment an atomic and write two floats to a buffer. Occasionlly, when the buffer fills, a caller will have to perform the merge operation.

TODOs

  • Provide encoding functionality
  • Benchmark against HDR Histogram
  • Evaluate accuracy against HDR Histogram at reasonable settings
  • Implement more scale functions
    • k_3
    • k_0 (uniform weight)
  • Describe use cases, comparisons, trade-offs
  • Implement trimmed mean

About

A concurrent, go(lang) implemention the t-digest streaming quantile estimation data structure.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages