package tdigest
Install
Dune Dependency
Authors
Maintainers
Sources
md5=a5253dec749621a8dc2484c92f087975
sha512=2eb1428a137fc2515af945e15a06cb49c3d7e8c0260f82b7f1391f94861ceea788f9f3a44671ed95d22f994a524cd0ce677913ac52aa0f3f589a28c1e664089c
Description
The TDigest is a data structure and algorithm for constructing an approximate distribution for a collection of real numbers presented as a stream.
The TDigest can estimate percentiles or quantiles extremely accurately even at the tails, while using a fraction of the space.
Additionally, the TDigest is concatenable, making it a good fit for distributed systems. The internal state of a TDigest can be exported as a binary string, and the concatenation of any number of those strings can then be imported to form a new TDigest.
Published: 29 Jun 2020
README
Tdigest
OCaml implementation of the TDigest algorithm.
The TDigest 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 TDigest can estimate percentiles or quantiles extremely accurately even at the tails, while using a fraction of the space.
Additionally, the TDigest is concatenable, making it a good fit for distributed systems. The internal state of a TDigest can be exported as a binary string, and the concatenation of any number of those strings can then be imported to form a new TDigest.
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 expensive intermediate computations worth caching.
Usage
The API is well documented here.
opam install tdigest
Dependencies (3)

core_kernel
>= "v0.13.0" & < "v0.15.0"

dune
>= "1.9.0"

ocaml
>= "4.08.1"
Used by
None
Conflicts
None