Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees

Nicholas Schiefer, Justin Y. Chen, Piotr Indyk +3

An $\epsilon$-approximate quantile sketch over a stream of $n$ inputs approximates the rank of any query point $q$ - that is, the number of input points less than $q$ - up to an…