## Generalizing Greenwald-Khanna Streaming Quantile Summaries for Weighted Inputs

Authors:
Sepehr Assadi, Nirmit Joshi, Milind Prabhu, Vihan Shah.

Abstract:
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 ∈ (0, 1], return a phi-quantile of S up to an
eps error. 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/ε)log (εn)) space [SIGMOD’01]. This bound
was recently proved to be optimal for all deterministic comparison-based summaries by Cormode
and Vesleý [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/ε)log (εn)) space and O(log(1/ε) + log log(εn)) update time per element to process a stream of length n (under some quite mild assumptions on the range of weights and ε). En route to this, we also simplify the original GK summaries for unweighted quantiles.

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/ε)log (εn)) space and O(log(1/ε) + log log(εn)) update time per element to process a stream of length n (under some quite mild assumptions on the range of weights and ε). En route to this, we also simplify the original GK summaries for unweighted quantiles.