Universal Sketches for the Frequency Negative Moments and Other Decreasing Streaming Sums
Universal Sketches for the Frequency Negative Moments and Other Decreasing Streaming Sums
复制标题
频率负矩和其他递减流总和的通用草图
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Stephen R. Chestnut
中科院分区：
文献类型：
--
作者：
V. Braverman;Stephen R. Chestnut
给定一个频率为$f_d$的流，对于$d\in[n]$，我们刻画了近似频率负矩$F_p=\sum所需的空间|f_d| ^p$，其中$p<0$，并且根据$n$，$\sum $和$m=\sum，对[n]$中具有非零频率的所有项$d\进行求和|f_d| $.为了实现这一点，我们实际上证明了一个更一般的结果。给定任何非负非增函数g，我们刻画了任何流算法所需的空间，该算法输出$\sum g（|f_d|）$，其中和再次是对具有非零频率的项。所需的存储表示在一个相对简单的非线性优化问题的解决方案的形式，该算法是通用的$（1\pm\m\f25）$-近似任何这样的总和，其中应用的功能是非负的，nonincreasing，并具有相同或更小的空间复杂度为$g$。这部分回答了纳尔逊提出的一个未决问题（IITK讲习班坎普尔，2009年）。
Given a stream with frequencies $f_d$, for $d\in[n]$, we characterize the space necessary for approximating the frequency negative moments $F_p=\sum |f_d|^p$, where $p<0$ and the sum is taken over all items $d\in[n]$ with nonzero frequency, in terms of $n$, $\epsilon$, and $m=\sum |f_d|$. To accomplish this, we actually prove a much more general result. Given any nonnegative and nonincreasing function $g$, we characterize the space necessary for any streaming algorithm that outputs a $(1\pm\epsilon)$-approximation to $\sum g(|f_d|)$, where again the sum is over items with nonzero frequency. The storage required is expressed in the form of the solution to a relatively simple nonlinear optimization problem, and the algorithm is universal for $(1\pm\epsilon)$-approximations to any such sum where the applied function is nonnegative, nonincreasing, and has the same or smaller space complexity as $g$. This partially answers an open question of Nelson (IITK Workshop Kanpur, 2009).