Generalizing Greenwald-Khanna Streaming Quantile Summaries for Weighted Inputs

Sepehr Assadi, Nirmit Joshi, Milind Prabhu, Vihan Shah

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 ϕ ∈ (0, 1], return a ϕ-quantile of S up to an ε error, i.e., return a ϕ-quantile with ϕ = ϕ ± ε. 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. 2012 ACM Subject Classification Theory of computation → Streaming, sublinear and near linear time algorithms; Theory of computation → Approximation algorithms analysis; Theory of computation → Data structures design and analysis.

Original languageEnglish (US)
Title of host publication26th International Conference on Database Theory, ICDT 2023
EditorsFloris Geerts, Brecht Vandevoort
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772709
DOIs
StatePublished - Mar 1 2023
Event26th International Conference on Database Theory, ICDT 2023 - Ioannina, Greece
Duration: Mar 28 2023Mar 31 2023

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume255
ISSN (Print)1868-8969

Conference

Conference26th International Conference on Database Theory, ICDT 2023
Country/TerritoryGreece
CityIoannina
Period3/28/233/31/23

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Quantile summaries
  • Rank estimation
  • Streaming algorithms

Fingerprint

Dive into the research topics of 'Generalizing Greenwald-Khanna Streaming Quantile Summaries for Weighted Inputs'. Together they form a unique fingerprint.

Cite this