Streaming Algorithms via Precision Sampling
Streaming Algorithms via Precision Sampling
复制标题
通过精确采样的流算法
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Krzysztof Onak
中科院分区：
文献类型：
--
作者：
Alexandr Andoni;Robert Krauthgamer;Krzysztof Onak
Indyk和Woodruff（Stoc 2005）引入的一种技术启发了数据流算法的最近进步。我们表明，从应用称为精确抽样的单个概率方法的应用中，许多结果很容易遵循。使用此方法，我们获得了简单的数据流算法，该算法维护输入向量$ x =（x_1，x_2，\ ldots，x_n）$的随机草图，这对于以下应用程序很有用：*估计$ f_k $ - $ x $的矩，对于$ k> 2 $。 ell_p（\ ell_q）$ for all $ p，q> 0 $。* $ \ ell_1 $采样，其中的目标是生产一个元素$ i $，概率（大约）$ | x_i | x_i |/\ | x \ | _1 $。它扩展到类似定义的$ \ ell_p $ -smpling，对于[1,2] $中的$ p \。对于所有这些应用程序，算法基本相同：按照精心挑选的随机向量将向量$ x $输入缩放，并对由此产生的向量进行重击估计算法。我们的草图是$ x $的线性函数，从而允许对向量$ x $的一般更新。精确采样本身解决了从[0,1] $中每个实际$ a_i \ in feal估算中估算总和$ \ sum_ {i = 1}^n a_i $的问题。更确切地说，估算器首先为[n] $中的每个$ i \ in（0,1] $选择所需的精度$ u_i \，然后收到添加$ u_i $中每个$ a_i $的估计值。其目标在保留``近似费用''$ \ sum_i（1/u_i）$的同时，提供对$ \ sum a_i $的良好近似值。这表明，只要$ \ sum a_i = \ omega（1）$，就可以使用仅$ O（n \ log n）$的总精度来实现良好的乘法近似。
A technique introduced by Indyk and Woodruff (STOC 2005) has inspired several recent advances in data-stream algorithms. We show that a number of these results follow easily from the application of a single probabilistic method called Precision Sampling. Using this method, we obtain simple data-stream algorithms that maintain a randomized sketch of an input vector $x=(x_1,x_2,\ldots,x_n)$, which is useful for the following applications:* Estimating the $F_k$-moment of $x$, for $k>2$.* Estimating the $\ell_p$-norm of $x$, for $p\in[1,2]$, with small update time.* Estimating cascaded norms $\ell_p(\ell_q)$ for all $p,q>0$.* $\ell_1$ sampling, where the goal is to produce an element $i$ with probability (approximately) $|x_i|/\|x\|_1$. It extends to similarly defined $\ell_p$-sampling, for $p\in [1,2]$. For all these applications the algorithm is essentially the same: scale the vector $x$ entry-wise by a well-chosen random vector, and run a heavy-hitter estimation algorithm on the resulting vector. Our sketch is a linear function of $x$, thereby allowing general updates to the vector $x$. Precision Sampling itself addresses the problem of estimating a sum $\sum_{i=1}^n a_i$ from weak estimates of each real $a_i\in[0,1]$. More precisely, the estimator first chooses a desired precision$u_i\in(0,1]$ for each $i\in[n]$, and then it receives an estimate of every $a_i$ within additive $u_i$. Its goal is to provide a good approximation to $\sum a_i$ while keeping a tab on the ``approximation cost'' $\sum_i (1/u_i)$. Here we refine previous work (Andoni, Krauthgamer, and Onak, FOCS 2010)which shows that as long as $\sum a_i=\Omega(1)$, a good multiplicative approximation can be achieved using total precision of only $O(n\log n)$.