## 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 language | English (US) |
---|---|

Title of host publication | 26th International Conference on Database Theory, ICDT 2023 |

Editors | Floris Geerts, Brecht Vandevoort |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959772709 |

DOIs | |

State | Published - Mar 1 2023 |

Event | 26th International Conference on Database Theory, ICDT 2023 - Ioannina, Greece Duration: Mar 28 2023 → Mar 31 2023 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 255 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 26th International Conference on Database Theory, ICDT 2023 |
---|---|

Country/Territory | Greece |

City | Ioannina |

Period | 3/28/23 → 3/31/23 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Quantile summaries
- Rank estimation
- Streaming algorithms