A Tight Lower Bound for Comparison-Based Quantile Summaries

Graham Cormode, Pavel Veselý

Quantiles, such as the median or percentiles, provide concise and useful information about the distribution of a collection of items, drawn from a totally ordered universe. We stud…