This repo contains a C++14 port of the implementation for the distributed quantile sketch algorithm DDSketch [1].

The port is based on the Python implementation - reference-commit

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.

The original implementation can be found here:

• sketches-java
• sketches-py
• sketches-go

The ddsketch.h header needs to be copied and included into the application you are building.

As the implementation uses some Modern C++ features, you will need to compile your application with -std=c++14

#include "ddsketch.h"

constexpr auto kDesiredRelativeAccuracy = 0.01;
ddsketch::DDSketch sketch(kDesiredRelativeAccuracy);

for (auto value = 1; value <= 100; ++value) {
    sketch.add(value);
}

const auto quantiles = {
    0.01, 0.05, 0.10, 0.20, 0.25,
    0.40, 0.50, 0.60, 0.75, 0.85,
    0.95, 0.96, 0.97, 0.98, 0.99
};

std::cout.precision(std::numeric_limits<double>::max_digits10);

for (const auto quantile : quantiles) {
    const auto computed_quantile = sketch.get_quantile_value(quantile);

    std::cout << "Quantile: " << quantile << "\n"
              << "Computed Quantile Value: " << computed_quantile << "\n";
}

The build system uses CMake. You can compile the example application by running the following commands:

mkdir build && cd build

cmake ../ -DBUILD_EXAMPLES=ON
cmake --build .

examples/DDSketch_Examples

Below, we will attempt to benchmark the insertion rate of the algorithm

Given the fact that ddsketch only computes a logarithm for every input value, the insert operations are quite fast.

Apache 2.0

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