UDDSketch: Accurate Tracking of Quantiles in Data Streams

Italo Epicoco, Catiuscia Melle, Massimo Cafaro, Marco Pulimeno, Giuseppe Morleo
4/18/2020
cs.DScs.DB

Official code: cafaro/UDDSketch (13 stars, last commit 2023-01-24).

Abstract

We present UDDSketch (Uniform DDSketch), a novel sketch for fast and accurate tracking of quantiles in data streams. This sketch is heavily inspired by the recently introduced DDSketch, and is based on a novel bucket collapsing procedure that allows overcoming the intrinsic limits of the corresponding DDSketch procedures. Indeed, the DDSketch bucket collapsing procedure does not allow the derivation of formal guarantees on the accuracy of quantile estimation for data which does not follow a sub-exponential distribution. On the contrary, UDDSketch is designed so that accuracy guarantees can be given over the full range of quantiles and for arbitrary distribution in input. Moreover, our algorithm fully exploits the budgeted memory adaptively in order to guarantee the best possible accuracy over the full range of quantiles. Extensive experimental results on synthetic datasets confirm the validity of our approach.

View on arXivView PDF

Code Implementations(1)

cafaro/UDDSketchOfficial100%
132C, CMakeJul 23, 20203 years agoNOASSERTION

Similar Papers

Sequential estimation of quantiles with applications to A/B-testing and best-arm identification

82% match2 repos872019

Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries

82% match1 repo202018

DDSketch: A fast and fully-mergeable quantile sketch with relative-error guarantees

81% match3 repos1872019

Calibrated Multi-Level Quantile Forecasting

80% match1 repo42025

Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees

80% match2023

Computing Extremely Accurate Quantiles Using t-Digests

79% match1 repo2.2k2019

Cite this paper

@article{epicoco2020uddsketch,
  title  = {UDDSketch: Accurate Tracking of Quantiles in Data Streams},
  author = {Italo Epicoco and Catiuscia Melle and Massimo Cafaro and Marco Pulimeno and Giuseppe Morleo},
  year   = {2020},
  eprint = {2004.08604},
  archivePrefix = {arXiv},
  url    = {https://arxiv.org/abs/2004.08604}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2004.08604.svg)](https://codeofpaper.com/paper/2004.08604)

Discussion