This repo contains the Python implementation of the distributed quantile sketch
algorithm DDSketch [1]. DDSketch has relative-error guarantees for any quantile
q in [0, 1]. That is if the true value of the qth-quantile is x then DDSketch
returns a value y such that |x-y| / x < e where e is the relative error
parameter. (The default here is set to 0.01.) DDSketch is also fully mergeable,
meaning that multiple sketches from distributed systems can be combined in a
central node.
Our default implementation, DDSketch, is guaranteed [1] to not grow too large
in size for any data that can be described by a distribution whose tails are
sub-exponential.
We also provide implementations (LogCollapsingLowestDenseDDSketch and
LogCollapsingHighestDenseDDSketch) where the q-quantile will be accurate up to
the specified relative error for q that is not too small (or large). Concretely,
the q-quantile will be accurate up to the specified relative error as long as it
belongs to one of the m bins kept by the sketch. If the data is time in
seconds, the default of m = 2048 covers 80 microseconds to 1 year.
To install this package, run pip install ddsketch, or clone the repo and run
python setup.py install. This package depends on numpy and protobuf. (The
protobuf dependency can be removed if it's not applicable.)
from ddsketch import DDSketch
sketch = DDSketch()
Add values to the sketch
import numpy as np
values = np.random.normal(size=500)
for v in values:
sketch.add(v)
Find the quantiles of values to within the relative error.
quantiles = [sketch.get_quantile_value(q) for q in [0.5, 0.75, 0.9, 1]]
Merge another DDSketch into sketch.
another_sketch = DDSketch()
other_values = np.random.normal(size=500)
for v in other_values:
another_sketch.add(v)
sketch.merge(another_sketch)
The quantiles of values concatenated with other_values are still accurate to within the relative error.
[1] Charles Masson and Jee E Rim and Homin K. Lee. DDSketch: A fast and fully-mergeable quantile sketch with relative-error guarantees. PVLDB, 12(12): 2195-2205, 2019. (The code referenced in the paper, including our implementation of the the Greenwald-Khanna (GK) algorithm, can be found at: https://github.com/DataDog/sketches-py/releases/tag/v0.1 )