Sketching, streaming and sub-linear space algorithms

a man to whom the difference between a pasture and a meadow seemed important, who got excited about sky color, who wrote a little poetry but not much fiction.

考虑这样一个问题，有一个无限长的 data stream，里面都是$[1,n]$ 中的整数。是否有一个算法，可以维护不同时刻的不同整数个数？

很显然，我们可以暴力存储下所有的整数并进行统计。但在 streaming 中，我们希望：

1. stream 只支持单次、单向扫描。除非把先前时刻的内容存储下来，否则无法获取 stream 中当前时刻之前的信息。
2. 不考虑时间复杂性，希望获得尽可能需要存储空间小的算法。

事实上，目前比较成熟的 streaming 算法都是 probabilistic estimation 答案，但是可以获得一个很好的空间复杂度，一般为$O(\text{poly}(\log N))$ 的水平。

# Distinct Elements Counting Problem

• 目标：估计 stream 中不同元素个数$DE$。我们希望给出一个答案$D$ 使得：

$$\text{Pr}[(1-\varepsilon)DE\leq D\leq(1+\varepsilon)DE]=1-P$$

其中$P$ 是一个常数。我们理解为，给出的答案以$1-P$ 的概率误差小于$1\pm \varepsilon$。实际中常常会出现$P$ 可以取任意小常数的情况，就容易见到$\text{Pr}=0.99$ 这样的证明。

• 一个简单的 gap 版本：给定一个$T>0$，给出一个算法输出 YES/NO 使得：
  • If $DE>(1+\varepsilon)T$, then answer YES with probability $1-P$.
  • If $DE<(1-\varepsilon)T$, then answer NO with probability $1-P$.

​ 很显然，我们可以并行地运行$\log_{1+\varepsilon}n$ 个 gap 版本，其中

$$T=1,1+\varepsilon,(1+\varepsilon)^2,...,n$$

​ 然后就可以得到原问题的答案在$[(1+\varepsilon)^k,(1-\varepsilon)(1+\varepsilon)^{k+t}]$ 中。其中，$t$ 是使得$(1-\varepsilon)(1+\varepsilon)^t\geq 1$ 的最小的整数$t$，即$t=\lceil \frac{-\log(1-\varepsilon)}{\log(1+\varepsilon)}\rceil$。

这样就可以得到一个可接受的解。复杂性的话总的复杂性显然需要乘上$O(\log_{1+\varepsilon}n)\approx\log n/\varepsilon$，因为并行地运行。然后也是因为并行，失败的概率也需要乘以这个数。

---

算法（gap 版本）：

• 随机选择一个集合$S\subseteq \{1,...,n\}$ 使得，对每个$i\in\{1,...,n\}$:

  $$\text{Pr}[i\in S]=\frac{1}{T}$$

• 维护$\text{Sum}_S(x)=\sum_i x_i$。其中，data stream 中每次得到$i$，就把$x_i$ 加一。$x$ 本来是一个全 0 的$n$ 维向量。

• 如果$\text{Sum}_S(x)>0$，则回答 YES，否则若$\text{Sum}_S(x)=0$，则回答 NO。

我们可以分析下这个算法。

首先很显然地，$\text{Pr}[\text{Sum}_S(x)=0]=(1-\frac{1}{T})^{DE}$。即$\text{Sum}_S(x)=0$ 时，当且仅当所有出现过的$i$ 都没被选择进$S$。

那么就有（因为$(1-1/T)^{DE}\approx e^{-DE/T}$ 若$T$ 足够大）：

• 当$DE>(1+\varepsilon)T$ 时，输出 NO 的概率小于$e^{-(1+\varepsilon)}<1/e-\varepsilon/3$。
• 当$DE<(1-\varepsilon)T$ 时，输出 NO 的概率大于$e^{-(1-\varepsilon)}>1/e+\varepsilon/3$。

这已经得到了一个 gap 的解。

---

我们可以进一步，选择一系列集合：

$$S_1,...,S_k,k=O(\log(1/P)/\varepsilon^2)$$

记$Z$ 为$k$ 个集合中，$\text{Sum}_{S_k}(x)=0$ 的集合数量。那么根据 Chernoff bound，有：

• 若$DE>(1+\varepsilon)T$，则$\text{Pr}[Z<k/e]>1-P$。
• 若$DE<(1-\varepsilon)T$，则$\text{Pr}[Z>k/e]>1-P$。

实际上，这就像选择一个稀疏的 01 矩阵$A_{k\times n}$。

其中，$A(i,j)=1$ 代表$j\in S_i$。那么最后的$\text{Sum}_{S_i}(x)$ 构成了一个列向量，为$A\times x$。

---

这个问题要的是统计$x$ 中不为 0 的数量，即$x$ 的$l_0$-norm。

同样我们可以推广问题，如果想去估计$x$ 的$l_p$-norm，即维护$(\sum_ix_i^p)^{1/p}$，是否有做法呢？目前已知结果：

• $p\in[0,2]$，那么只需要$O(\text{poly}(\log n))$ 的空间。
• 对$p>2$，需要$O(n^{1-2/p}\text{poly}(\log n))$ 的空间。