  Estimating quantiles, like the median or percentiles, is a fundamental task
in data mining and data science. A (streaming) quantile summary is a data
structure that can process a set S of n elements in a streaming fashion and at
the end, for any phi in (0,1], return a phi-quantile of S up to an eps error,
i.e., return a phi'-quantile with phi'=phi +- eps. We are particularly
interested in comparison-based summaries that only compare elements of the
universe under a total ordering and are otherwise completely oblivious of the
universe. The best known deterministic quantile summary is the 20-year old
Greenwald-Khanna (GK) summary that uses O((1/eps) log(eps n)) space
[SIGMOD'01]. This bound was recently proved to be optimal for all deterministic
comparison-based summaries by Cormode and Vesle\'y [PODS'20].
  In this paper, we study weighted quantiles, a generalization of the quantiles
problem, where each element arrives with a positive integer weight which
denotes the number of copies of that element being inserted. The only known
method of handling weighted inputs via GK summaries is the naive approach of
breaking each weighted element into multiple unweighted items and feeding them
one by one to the summary, which results in a prohibitively large update time
(proportional to the maximum weight of input elements).
  We give the first non-trivial extension of GK summaries for weighted inputs
and show that it takes O((1/eps) log(eps n)) space and O(log(1/eps)+ log
log(eps n)) update time per element to process a stream of length n (under some
quite mild assumptions on the range of weights and eps). En route to this, we
also simplify the original GK summaries for unweighted quantiles.
