A Randomized Online Quantile Summary in O((1/ε) log(1/ε)) Words
A Randomized Online Quantile Summary in O((1/ε) log(1/ε)) Words
复制标题
O((1/ε) log(1/ε)) 个字的随机在线分位数摘要
作者：
David Felber;R. Ostrovsky
分位数摘要是一种数据结构，近似于 $varepsilon$ 相对误差（更大的基础数据集的顺序统计）。
在本文中，我们为收银机数据输入模型和比较数据域模型开发了一个随机在线分位数摘要，该模型使用 $O(frac{1}{varepsilon} log frac{1}{varepsilon})$ 个内存字数。这改进了 Agarwal 等人之前提出的 $O(frac{1}{varepsilon} log^{3/2} frac{1}{varepsilon})$ 的最佳上限。等人。 （PODS 2012）。此外，根据 Hung 和 Ting 的下限（FAW 2010），比较模型的确定性总结在空间复杂度方面无法胜过我们的随机总结。最后，我们的摘要有一个很好的特性，即 $O(frac{1}{varepsilon} log frac{1}{varepsilon})$ 个单词足以确保成功概率为 $1 - e^{- ext{poly}(1/varepsilon)}$。
A quantile summary is a data structure that approximates to $varepsilon$-relative error the order statistics of a much larger underlying dataset.
In this paper we develop a randomized online quantile summary for the cash register data input model and comparison data domain model that uses $O(frac{1}{varepsilon} log frac{1}{varepsilon})$ words of memory. This improves upon the previous best upper bound of $O(frac{1}{varepsilon} log^{3/2} frac{1}{varepsilon})$ by Agarwal et. al. (PODS 2012). Further, by a lower bound of Hung and Ting (FAW 2010) no deterministic summary for the comparison model can outperform our randomized summary in terms of space complexity. Lastly, our summary has the nice property that $O(frac{1}{varepsilon} log frac{1}{varepsilon})$ words suffice to ensure that the success probability is $1 - e^{- ext{poly}(1/varepsilon)}$.