Revisiting Norm Estimation in Data Streams
Revisiting Norm Estimation in Data Streams
复制标题
重新审视数据流中的范数估计
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
David P. Woodruff
中科院分区：
文献类型：
--
作者：
D. Kane;Jelani Nelson;David P. Woodruff
数据流中估计PTH矩f_p（p非负和真实）的问题如下。有一个从0开始的向量X，并且表单x_i <-x_i + V的许多更新顺序出现在流中。该算法还接收一个错误参数0 <eps <1。然后，该目标是输出一个近似值，其中大多数EPS在f_p = || x || x || _p^p中输出。
以前，众所周知，当且仅当p <= 2时，可以实现多组载体空间（在矢量长度n中）。
（*）0 <p <2的最佳空间算法与以前的算法不同，该算法对1/eps但对n的次优依赖性具有最佳的依赖性，但不依赖于通用的pseudorandom生成器。
（*）P = 0的近乎最佳空间算法，具有最佳的更新和查询时间。
（*）“不同的元素”问题（p = 0，所有更新均具有v = 1）的近乎最佳空间算法，并具有最佳的更新和查询时间。
（*）改进的L_2-> L_2尺寸降低流。
（*）新的1通行下限，以显示我们算法的最优性和近距离的最佳性，以及某些先前的算法（p = 2的“ AMS草图”，以及Feigenbaum等人的L_1-差异算法。 。
作为我们工作的推论，我们还获得了矩估计问题的复杂性：f_0 in 1 pass vs. 2通过，p = 0 vs. p> 0，而f_0具有严格的正更新与任意更新。
The problem of estimating the pth moment F_p (p nonnegative and real) in data streams is as follows. There is a vector x which starts at 0, and many updates of the form x_i <-- x_i + v come sequentially in a stream. The algorithm also receives an error parameter 0 < eps < 1. The goal is then to output an approximation with relative error at most eps to F_p = ||x||_p^p.
Previously, it was known that polylogarithmic space (in the vector length n) was achievable if and only if p <= 2. We make several new contributions in this regime, including:
(*) An optimal space algorithm for 0 < p < 2, which, unlike previous algorithms which had optimal dependence on 1/eps but sub-optimal dependence on n, does not rely on a generic pseudorandom generator.
(*) A near-optimal space algorithm for p = 0 with optimal update and query time.
(*) A near-optimal space algorithm for the "distinct elements" problem (p = 0 and all updates have v = 1) with optimal update and query time.
(*) Improved L_2 --> L_2 dimensionality reduction in a stream.
(*) New 1-pass lower bounds to show optimality and near-optimality of our algorithms, as well as of some previous algorithms (the "AMS sketch" for p = 2, and the L_1-difference algorithm of Feigenbaum et al.).
As corollaries of our work, we also obtain a few separations in the complexity of moment estimation problems: F_0 in 1 pass vs. 2 passes, p = 0 vs. p > 0, and F_0 with strictly positive updates vs. arbitrary updates.