  Estimating quantiles is one of the foundational problems of data sketching.
Given $n$ elements $x_1, x_2, \dots, x_n$ from some universe of size $U$
arriving in a data stream, a quantile sketch estimates the rank of any element
with additive error at most $\varepsilon n$. A low-space algorithm solving this
task has applications in database systems, network measurement, load balancing,
and many other practical scenarios.
  Current quantile estimation algorithms described as optimal include the GK
sketch (Greenwald and Khanna 2001) using $O(\varepsilon^{-1} \log n)$ words
(deterministic) and the KLL sketch (Karnin, Lang, and Liberty 2016) using
$O(\varepsilon^{-1} \log\log(1/\delta))$ words (randomized, with failure
probability $\delta$). However, both algorithms are only optimal in the
comparison-based model, whereas most typical applications involve streams of
integers that the sketch can use aside from making comparisons.
  If we go beyond the comparison-based model, the deterministic q-digest sketch
(Shrivastava, Buragohain, Agrawal, and Suri 2004) achieves a space complexity
of $O(\varepsilon^{-1}\log U)$ words, which is incomparable to the
previously-mentioned sketches. It has long been asked whether there is a
quantile sketch using $O(\varepsilon^{-1})$ words of space (which is optimal as
long as $n \leq \mathrm{poly}(U)$). In this work, we present a deterministic
algorithm using $O(\varepsilon^{-1})$ words, resolving this line of work.
