Distinct Elements 问题

Distinct Elements 把频率向量压成“哪些坐标最终非零”这一集合信息：同一键的重复次数不增加答案，删除却可能让一个坐标重新退出支持集。因此事件抽样会被高频键偏置，而能否处理删除又取决于摘要是否记住净频率而非历史上见过与否。

一个可追踪的实例 ​

插入流

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

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

更新模型决定问题版本 ​

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

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

在只需近似基数且可接受随机误差时，Flajolet–Martin 与 HyperLogLog公理库Flajolet–Martin 与 HyperLogLogFlajolet-Martin · HyperLogLog · HLL用哈希位串中的罕见前导零事件估计不同元素数，并以多寄存器调和聚合降低方差。用哈希值前导零和分桶寄存器压缩已见集合。它们适合 insertion-only、去重计数和参数一致的逐寄存器合并；一般删除流、对抗性哈希输入或不兼容种子的摘要不能直接沿用同一估计与合并保证。

单遍精确计数为什么需要大状态 ​

对宇宙大小 $U=2n$、流长 $m=n+1$，即使保证前 $n$ 项全异，末项至多制造一对重复，单遍精确计数仍需最坏空间 $\mathrm{\Omega }(n)$ bits，允许每个固定流至多 $1/3$ 的错误也不例外。通信下界的完整证明公理库通信下界归约范式Communication lower-bound reduction pattern · Communication reduction for lower bounds用固定长度的 INDEX 编码，把单遍精确不同元素计数的完整内存状态变成一次消息，并逐项保留错误、随机性和空间单位。用前缀 $(1,x_1),\dots ,(n,x_n)$ 编码任意位串，末项 $(i,1)$ 使 $F_0=n+1-x_i$。若状态太短，把它交给持有 $i$ 的 Bob，就会得到违反 INDEX 下界的单向协议。

这里“精确”修饰成功事件中的数值，算法本身可以随机且偶尔失败。下界也不依赖大量重复：全异与仅一对重复之间已经足以携带一 bit 的答案。$U$-bit 已见表加一个计数器给出本参数族的 $O(n)$-bit 上界，所以这一族的单遍精确空间量级为 $\mathrm{\Theta }(n)$。

这组输入的答案只有 $n$ 与 $n+1$。加性误差严格小于 $1/2$ 仍可区分，但相对误差需要 $\epsilon <1/(2n+1)$ 才让两个保证区间不重叠。因此该例没有证明常数相对误差也需要线性空间；上述近似摘要正是在更宽的误差契约下工作。

求解路线与边界 ​

精确维护所有已见键可以直接得到答案，但在大宇宙中可能占用与支持集近似线性的空间。近似算法用随机化换取小空间；尾零统计、分桶寄存器和分层采样是不同求解路线，它们通过不同的统计量和哈希机制估计同一个支持集大小。

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