论文标题
具有较大近似因子的流算法
Streaming Algorithms with Large Approximation Factors
论文作者
论文摘要
我们在流媒体模型中对经典问题进行了广泛的研究，并在我们允许近似因子$α$的设置中插入和删除，以大于$ 1 $。此类算法比通常的设置要使用的内存明显少得多，该设置的$α= 1+ε$对于$ε\ in（0,1）$。我们研究了大近似值，以解决草图和流中的许多问题，以下是我们的一些结果。 对于$ \ ell_p $ norm/quasinorm $ \ | x \ | | _p $ a $ n $ -dimensional vector $ x $，$ 0 <p \ le 2 $，我们表明，获得$ \ poly（n）$ - 近似值需要获得$ O（1）$ - o（1）$ - 近似$ - 近似$ m m = n^n^n^n^n. 为了估计$ \ ell_p $ norm，$ p> 2 $，我们显示了$ o（n^{1-2/p}（\ log n \ log block break \ log m）/α^{2}）$位的上限，用于$α$ - approximation，并提供匹配的下限，并提供$α\ egeq的整个范围。 对于$ \ ell_2 $ -heavy击球手的问题，我们表明已知的$ω（k \ log n \ log m）$位的已知下限用于识别$（1/k）$ - 重型击球手即使我们被允许输出$ 1/（αk）$的输出物品（几乎是$ a $ a $ a $ a $ a $ a $ a $ a $ 1），即使我们可以输出$ 1/（αk）$ 1- $ 1- $ 1（只要1 $ 1）。我们还获得了线性草图的下限，即使对于恒定概率算法也是紧密的。 为了估算不同元素的数字$ \ ell_0 $，我们使用$ o（t \ log \ log \ log m）$ abt oss oss of $ n^{1/t} $ - 近似算法，以及$ω（t）$位的下限，均不包括随机位的存储。
We initiate a broad study of classical problems in the streaming model with insertions and deletions in the setting where we allow the approximation factor $α$ to be much larger than $1$. Such algorithms can use significantly less memory than the usual setting for which $α= 1+ε$ for an $ε\in (0,1)$. We study large approximations for a number of problems in sketching and streaming and the following are some of our results. For the $\ell_p$ norm/quasinorm $\|x\|_p$ of an $n$-dimensional vector $x$, $0 < p \le 2$, we show that obtaining a $\poly(n)$-approximation requires the same amount of memory as obtaining an $O(1)$-approximation for any $M = n^{Θ(1)}$. For estimating the $\ell_p$ norm, $p > 2$, we show an upper bound of $O(n^{1-2/p} (\log n \allowbreak \log M)/α^{2})$ bits for an $α$-approximation, and give a matching lower bound, for almost the full range of $α\geq 1$ for linear sketches. For the $\ell_2$-heavy hitters problem, we show that the known lower bound of $Ω(k \log n\log M)$ bits for identifying $(1/k)$-heavy hitters holds even if we are allowed to output items that are $1/(αk)$-heavy, for almost the full range of $α$, provided the algorithm succeeds with probability $1-O(1/n)$. We also obtain a lower bound for linear sketches that is tight even for constant probability algorithms. For estimating the number $\ell_0$ of distinct elements, we give an $n^{1/t}$-approximation algorithm using $O(t\log \log M)$ bits of space, as well as a lower bound of $Ω(t)$ bits, both excluding the storage of random bits.
