  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.

Data Structures and Algorithms;Databases