Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Estimating quantiles is one of the most basic problems in data sketching. In this problem, a stream x₁, x₂, x₃,…, x_n of elements from some universe of size U, a rank r, and an accuracy ε are given. The goal is to give a space-efficient algorithm that outputs an element with rank between r-εn and r+εn. For example, this captures median estimation and 99th percentile estimation.

It has long been known that a quantile sketch can be made more space-efficient than storing every element individually (which would take n·log(U) memory). The previous best algorithms all improved substantially on nlogU but did not meet the lower bound of Ω(ε^-1·(log(n)+log(U))) . In this talk, we’ll describe a deterministic quantile sketch that uses the optimal O(ε^-1·(log(n)+log(U))) bits of memory.

This is joint work with Mihir Singhal and Hongxun Wu.