Theory meets Practice at the Median: A Worst Case Comparison of Relative Error Quantile Algorithms
Theory meets Practice at the Median: A Worst Case Comparison of Relative Error Quantile Algorithms
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 queries using a small amount of space, thus helping to understand the tails of the input distribution. Namely, we focus on two recent …