An efficient algorithm for approximate biased quantile computation in data streams
An efficient algorithm for approximate biased quantile computation in data streams
复制标题
数据流中近似有偏分位数计算的有效算法
DOI：
10.1145/1321440.1321601
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Wei Wang
中科院分区：
文献类型：
--
作者：
Qi Zhang;Wei Wang
本文提出了一种在大数据流中计算近似有偏分位数的有效算法。我们的算法计算可分解的偏置分位数摘要固定大小的块和动态维护偏置分位数摘要为整个流的指数直方图在块的分位数摘要。该算法计算效率高，平均计算量为<i>O</i>（log（<sup>1</sup><$<sub>∈</sub>log（∈<i>n</i>），空间占用率为<i>O</i>（<sup>log 3</sup>∈<i>n <$</i><sub>∈</sub>）。我们的算法不假设流大小或流中数据值的范围的先验知识。在实践中，我们的算法是能够有效地维护超过数千万的观察大型数据流的摘要，并实现了显着的性能改进比以前的算法。
We propose an efficient algorithm for approximate biased quantile computation in large data streams. Our algorithm computes decomposable biased quantile summaries on fixed sized blocks and dynamically maintains the biased quantile summary for the entire stream as the exponential histogram over the block-wise quantile summaries. The algorithm is computationally efficient and achieves an amortized computational cost of <i>O</i>(log(<sup>1</sup>⁄<sub>∈</sub>log(∈<i>n</i>))) and a space requirement of <i>O</i>(<sup>log3</sup>∈<i>n</i>↬<sub>∈</sub>). Our algorithm does not assume prior knowledge of the stream sizes or the range of data values in the streams. In practice, our algorithm is able to efficiently maintain summaries over large data streams with over tens of millions of observations and achieves significant performance improvement over prior algorithms.