gazagnaire.org / ocaml-ckms
Streaming quantiles with targeted error bounds (CKMS)
0
Fork 0

Configure Feed

Select the types of activity you want to include in your feed.

OCaml 86.8%
Dune 5.2%
Other 8.1%
5 1 0

Clone this repository

https://git.vm.fail/gazagnaire.org/ocaml-ckms https://git.vm.fail/did:plc:itdclxpyk3lm4k5u7owdtzcc
ssh://git@git.recoil.org:2222/gazagnaire.org/ocaml-ckms ssh://git@git.recoil.org:2222/did:plc:itdclxpyk3lm4k5u7owdtzcc

For self-hosted knots, clone URLs may differ based on your setup.


Download tar.gz Download .zip
README.md

ckms#

Streaming quantiles with targeted error bounds (CKMS).

A pure-OCaml implementation of the Cormode-Korn-Muthukrishnan-Srivastava algorithm for biased quantiles over data streams (ICDE 2005). It estimates the value at chosen quantiles (p50/p90/p99/...) in memory bounded by the number of targets and their precision, not by the number of observations, with a guaranteed rank error per target. A sliding-time-window estimator reports quantiles over recent observations, as a Prometheus summary does; the clock is injected, so the core stays pure and tests drive it with a mock.

Install#

opam install ckms

If opam cannot find the package, it may not yet be released in the public opam-repository. Add the overlay repository, then install it:

$ opam repo add samoht https://tangled.org/gazagnaire.org/opam-overlay.git
$ opam update
$ opam install ckms

API#

The Ckms module (lib/ckms.mli) is the whole interface: create an estimator for a set of targets, insert observations, and query the estimated value at a quantile.

License#

ISC. See LICENSE.md.