layout: doc_page

KLL Sketch C++ Example

#include <iostream>
#include <fstream>
#include <random>
#include <chrono>

#include <kll_sketch.hpp>

//simplified file operations and no error handling for clarity
int main(int argc, char **argv) {
  // this section generates two sketches from random data and serializes them into files
  {
    std::default_random_engine generator(std::chrono::system_clock::now().time_since_epoch().count());
    std::normal_distribution<float> nd(0, 1); // mean=0, stddev=1

    datasketches::kll_sketch<float> sketch1; // default k=200
    for (int i = 0; i < 10000; i++) {
      sketch1.update(nd(generator)); // mean=0, stddev=1
    }
    std::ofstream os1("kll_sketch_float1.bin");
    sketch1.serialize(os1);

    datasketches::kll_sketch<float> sketch2; // default k=200
    for (int i = 0; i < 10000; i++) {
      sketch2.update(nd(generator) + 1); // shift the mean for the second sketch
    }
    std::ofstream os2("kll_sketch_float2.bin");
    sketch2.serialize(os2);
  }

  // this section deserializes the sketches, produces a union and prints some results
  {
    std::ifstream is1("kll_sketch_float1.bin");
    auto sketch1 = datasketches::kll_sketch<float>::deserialize(is1);

    std::ifstream is2("kll_sketch_float2.bin");
    auto sketch2 = datasketches::kll_sketch<float>::deserialize(is2);

    // we could merge sketch2 into sketch1 or the other way around
    // this is an example of using a new sketch as a union and keeping the original sketches intact
    datasketches::kll_sketch<float> u; // default k=200
    u.merge(sketch1);
    u.merge(sketch2);

    // Debug output
    std::cout << u.to_string();

    std::cout << "Min: " << u.get_min_item() << std::endl;
    std::cout << "Max: " << u.get_max_item() << std::endl;
    auto quantiles = u.get_quantiles((double[3]){0.5, 0.75, 0.9}, 3);
    std::cout << "Quantiles: 0.5 (median), 0.75, 0.9:\n";
    std::cout << quantiles[0] << ", " << quantiles[1] << ", " << quantiles[2] << std::endl;

    std::cout << "Probability Histogram: estimated probability mass in 4 bins: (-inf, -2), [-2, 0), [0, 2), [2, +inf)" << std::endl;
    const float split_points[] {-2, 0, 2};
    const int num_split_points = 3;
    auto pmf = u.get_PMF(split_points, num_split_points);
    std::cout << pmf[0] << ", " << pmf[1] << ", " << pmf[2] << ", " << pmf[3] << std::endl;

    std::cout << "Frequency Histogram: estimated number of original values in the same bins" << std::endl;
    const int num_bins = num_split_points + 1;
    int histogram[num_bins];
    for (int i = 0; i < num_bins; i++) {
      histogram[i] = pmf[i] * u.get_n(); // scale the fractions by the total count of values
    }
    std::cout << histogram[0] << ", " << histogram[1] << ", " << histogram[2] << ", " << histogram[3] << std::endl;
  }

  return 0;
}

Output (will be slightly different every time due to random input):
### KLL sketch summary:
   K              : 200
   min K          : 200
   M              : 8
   N              : 20000
   Epsilon        : 1.33%
   Epsilon PMF    : 1.65%
   Empty          : false
   Estimation mode: true
   Levels         : 7
   Sorted         : false
   Capacity items : 565
   Retained items : 394
   Min item      : -3.75
   Max item      : 4.6
### End sketch summary
Min: -3.75359
Max: 4.60465
Quantiles: 0.5 (median), 0.75, 0.9:
0.508168, 1.25914, 1.938
Probability Histogram: estimated probability mass in 4 bins: (-inf, -2), [-2, 0), [0, 2), [2, +inf)
0.0118, 0.3134, 0.58475, 0.09005
Frequency Histogram: estimated number of original values in the same bins
236, 6268, 11695, 1800