2 papers
cs.DS2021
Theory meets Practice at the Median: a worst case comparison of relative error quantile algorithms
Graham Cormode, Abhinav Mishra, Joseph Ross +1
Estimating the distribution and quantiles of data is a foundational task in data mining and data science. We study algorithms which provide accurate results for extreme quantile qu…
cs.DS2020
Asymmetric scale functions for -digests
Joseph Ross
The -digest is a data structure that can be queried for approximate quantiles, with greater accuracy near the minimum and maximum of the distribution. We develop a -digest va…