Distinct Elements 问题

问题接口 ​

在数据流模型公理库数据流算法模型Data-stream model · Streaming algorithm输入顺序到达且不能保存全文，以扫描趟数、工作空间、处理时间和输出保证评价算法。中，设键宇宙为 $[U]=\{1,\dots ,U\}$。流由更新 $(i_t,{\mathrm{\Delta }}_t)$ 组成，处理完前 $m$ 个更新后，键 $i$ 的频率为

$$f_i=\sum _{t:i_t=i}{\mathrm{\Delta }}_t.$$

Distinct Elements 问题要求输出当前频率向量支持集的大小

$$D=|\{i\in [U]:f_i\ne 0\}|.$$

这个量也记作零阶频率矩公理库频率矩问题Frequency moments用 F_k 汇总频率向量，统一不同项数、流长与重复集中度目标。 $F_0$，但频率矩只是等价记号，不是提出问题所必需的前置。问题关心有多少种键出现，而不是一共处理了多少次更新：某个键出现一次或一百万次，只要最终频率非零，都只贡献 $1$。

输出契约 ​

精确版本要求返回 $D$。流式近似版本通常给定精度 $\epsilon \in (0,1)$ 和失败概率 $\delta \in (0,1)$，要求输出 $\hat{D}$，使

$$\text{Pr}[(1-\epsilon )D\le \hat{D}\le (1+\epsilon )D]\ge 1-\delta .$$

概率来自算法内部随机性；若输入本身也随机，必须另行说明分布，不能把两者合并成一个未注明来源的“平均准确率”。当 $D=0$ 时，相对误差区间退化，通常约定算法必须精确输出 $0$。

完整的资源保证还要写明遍数、工作空间、每次更新时间和最终查询时间。空间可能依赖 $\epsilon ,\delta ,\log U$，而流长 $m$、宇宙大小 $U$ 与答案 $D$ 是不同参数，不能在公式里互换。

一个可追踪的实例 ​

插入流

$$a,b,a,c,b,b$$

共有六次到达，却只有三个不同键，所以 $D=3$。若再到达一千个 $a$，答案仍为 $3$。这正是独立访客、不同查询词和唯一设备数等应用的共同接口：重复活跃度不应增加基数。

对流位置作均匀采样不能直接解决这个问题。高频键占据更多位置，因而更容易进入样本；样本分布针对出现次数，而目标对每种键只计一次。有效摘要必须控制这种频率偏差，而不能把“随机抽到一些事件”当成“随机抽到一些不同键”。

更新模型决定问题版本 ​

在 insertion-only 模型中，${\mathrm{\Delta }}_t=1$，支持集只增不减。Strict turnstile 允许删除，但每个中间时刻保持 $f_i\ge 0$；general turnstile 还允许中间频率为负。三者虽然共享同一个输出公式，却给算法不同的信息恢复义务。

例如先插入 $a,b$，再删除 $a$，最终答案应从 $2$ 降为 $1$。一个只记住“见过哪些键”或只会单调增加的插入式摘要无法知道 $a$ 已离开支持集。支持删除的算法必须重新证明其状态能反映最终非零频率，不能通过忽略删除把插入算法直接推广。

求解路线与边界 ​

精确维护所有已见键可以直接得到答案，但在大宇宙中可能占用与支持集近似线性的空间。近似算法用随机化换取小空间；尾零统计、分桶寄存器和分层采样是不同求解路线，其估计量、方差控制、哈希要求与合并规则应在算法专页展开。本页只规定它们共同求解的对象和保证。

分布式合并也不是问题定义自动赠送的性质。两个摘要只有在参数、随机种子和合并操作兼容时，才可能等价于集中处理联合流；重复合并同一分片还可能把传输重放误当成新更新。若输入允许自适应地观察摘要后选择后续键，也必须在模型中声明对手能力，因为这会改变概率保证。

参考资料

• Flajolet, Martin, “Probabilistic Counting Algorithms,” JCSS, 1985.
• Alon, Matias, Szegedy, 1999.