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
复制标题
理论与实践的中位数：相对误差分位数算法的最坏情况比较
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
P. Vesel'y
中科院分区：
文献类型：
--
作者：
Graham Cormode;Abhinav Mishra;Joseph Ross;P. Vesel'y
估计数据的分布和分位数是数据挖掘和数据科学中的一项基本任务。我们研究的算法，提供准确的结果，极端分位数查询使用少量的空间，从而有助于了解输入分布的尾部。也就是说，我们专注于两个最近的国家的最先进的解决方案：t-digest和ReqSketch。虽然t-digest是一种流行的紧凑摘要，在各种设置中都能很好地工作，但ReqSketch具有形式上的准确性保证，其代价是随着新观察的插入而增加。在这项工作中，我们提供了洞察哪些条件使一个比另一个更可取。也就是说，我们展示了如何构建输入的t-摘要，诱导一个几乎任意大的错误，并证明它无法提供准确的结果，即使在i.i.d.。来自高度非均匀分布的样本。我们对ReqSketch提出了实际的改进，使其比t-digest更快，而其误差在任何实例上都保持有界。尽管如此，我们的研究结果证实，t-digest在实践中遇到的“非对抗性”数据上仍然更准确。
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 state-of-the-art solutions: t-digest and ReqSketch. While t-digest is a popular compact summary which works well in a variety of settings, ReqSketch comes with formal accuracy guarantees at the cost of its size growing as new observations are inserted. In this work, we provide insight into which conditions make one preferable to the other. Namely, we show how to construct inputs for t-digest that induce an almost arbitrarily large error and demonstrate that it fails to provide accurate results even on i.i.d. samples from a highly non-uniform distribution. We propose practical improvements to ReqSketch, making it faster than t-digest, while its error stays bounded on any instance. Still, our results confirm that t-digest remains more accurate on the "non-adversarial" data encountered in practice.
相对误差流分位数
影响因子：
2.5
作者：
Cormode, Graham;Karnin, Zohar;Liberty, Edo;Thaler, Justin;Veselý, Pavel
通讯作者：
Veselý, Pavel