package tdigest

Build not checked
  1. Overview
  2. Docs
OCaml implementation of the T-Digest algorithm

Install

dune-project
 Dependency

Authors

Maintainers

Sources

2.1.2.tar.gz
md5=1f200a6b32f0d19ee0e33d77584fa9bc
sha512=8649e06a21f602c084c85c21f5d98a9f9332d603cc5bfda994566c9620f73863d0bf741bd322015dffa5ab1c26c42b97faead69dc1d514128eeb592e06f81847

Description

The T-Digest is a data structure and algorithm for constructing an approximate distribution for a collection of real numbers presented as a stream.

The T-Digest can estimate percentiles or quantiles extremely accurately even at the tails, while using a fraction of the space.

Additionally, the T-Digest is concatenable, making it a good fit for distributed systems. The internal state of a T-Digest can be exported as a binary string, and the concatenation of any number of those strings can then be imported to form a new T-Digest.

Added to opam-repository:

README

Tdigest

OCaml implementation of the T-Digest algorithm.

let td =
  Tdigest.create ()
  |> Tdigest.add_list [ 10.0; 11.0; 12.0; 13.0 ]
in

Tdigest.percentiles td [ 0.; 0.25; 0.5; 0.75; 1. ]
(* [ Some 10; Some 10.5; Some 11.5; Some 12.5; Some 13 ] *)

Tdigest.p_ranks td [ 9.; 10.; 11.; 12.; 13.; 14. ]
(* [ Some 0; Some 0.125; Some 0.375; Some 0.625; Some 0.875; Some 1 ] *)

The T-Digest is a data structure and algorithm for constructing an approximate distribution for a collection of real numbers presented as a stream.

The median of a list of medians is not necessarily equal to the median of the whole dataset. The median (p50), p95, and p99 are critical measures that are expensive to compute due to their requirement of having the entire sorted dataset present in one place.

The T-Digest can estimate percentiles or quantiles extremely accurately even at the tails, while using a fraction of the space.

Additionally, the T-Digest is concatenable, making it a good fit for distributed systems. The internal state of a T-Digest can be exported as a binary string, and the concatenation of any number of those strings can then be imported to form a new T-Digest.

let combined = Tdigest.merge [ td1; td2; td3 ] in

A T-Digest's state can be stored in a database VARCHAR/TEXT column and multiple such states can be merged by concatenating strings:

SELECT
  STRING_AGG(M.tdigest_state) AS concat_state
FROM my_table AS M
let combined = Tdigest.of_string concat_state in

Links:

This library started off as a port of Will Welch's JavaScript implementation, down to the unit tests. However some modifications have been made to adapt it to OCaml, the most important one being immutability. As such, almost every function in the Tdigest module return a new Tdigest.t, including "reading" ones since they may trigger intermediate computations worth caching.

Usage

The API is well documented here.

opam install tdigest

Performance

On a 2018 MacBook Pro, it can incorporate 1,000,000 random floating points in just 770ms.

Exporting and importing state (to_string/of_string) is essentially free.

Dependencies (3)

  1. core >= "v0.15.0" & < "v0.17.0"
  2. dune >= "1.9.0"
  3. ocaml >= "4.10.0"

Dev Dependencies

None

Optional Dependencies

None

Used by

None

Conflicts

None

Build status

Results of building tdigest with each compiler on check.ci.ocaml.org, run of against opam-repository 8d8d144. All results for this package.

Each result links to its build log. To keep crawlers from overloading the site, build logs require a GitHub sign-in (see ocurrent/opam-health-check). On your first log, GitHub asks you to “Authorize opam-health-check”, the OCurrent app that runs these checks; it sees only your public profile, not your repositories. The sign-in lasts 30 days.

This version is not in the latest run; the versions below are.

Version OCaml 4.11 OCaml 4.14 OCaml 5.2 OCaml 5.4 OCaml 5.5
2.2.1 n/a n/a good good good
2.2.0 n/a good good n/a n/a
2.1.3 good good good n/a n/a
  • good Package successfully built
  • partial One of the dependencies failed to build
  • bad Package failed to build
  • n/a Package is not available in this environment
  • internal Internal failure