  Estimating the distribution and quantiles of data is a foundational task in
data mining and data science. We study algorithms which provide accurate
results for extreme quantile queries using a small amount of space, thus
helping to understand the tails of the input distribution. Namely, we focus on
two recent state-of-the-art solutions: $t$-digest and ReqSketch. While
$t$-digest is a popular compact summary which works well in a variety of
settings, ReqSketch comes with formal accuracy guarantees at the cost of its
size growing as new observations are inserted. In this work, we provide insight
into which conditions make one preferable to the other. Namely, we show how to
construct inputs for $t$-digest that induce an almost arbitrarily large error
and demonstrate that it fails to provide accurate results even on i.i.d.
samples from a highly non-uniform distribution. We propose practical
improvements to ReqSketch, making it faster than $t$-digest, while its error
stays bounded on any instance. Still, our results confirm that $t$-digest
remains more accurate on the "non-adversarial" data encountered in practice.
