数据流算法模型

一趟实例的状态演化 ​

处理同一包源地址流时，精确频率表、distinct 摘要与 heavy-hitter 摘要回答不同函数，状态和误差保证也不同。“流式”只规定资源协议，不能推出共同的统计接口。

若要求每次更新后立即输出，查询或解码时间会进入逐项延迟；只在流末输出则可把部分工作推迟到终点。持续监控与 one-shot summary 必须分别计费。

模型边界 ​

是否知道 $m$、宇宙大小、随机种子是否公开、空间按 bit 还是 word 都影响结论。多趟算法可用少空间反复扫描；外存模型允许随机访问磁盘，约束不同。通信复杂度归约常给流空间下界。

滑动窗口只统计最近 $W$ 项，时间衰减给旧项降权，分布式流还要求可合并；它们都在根模型上增加语义。若保存完整流的外部日志，也应把这部分线性外部空间计入资源。

状态机执行轨迹 ​

设状态只有 64 个 32-bit words。更新到来时，算法只能用当前状态、更新与固定随机种子计算下一状态，不能再次读取早先记录。对地址流 a,b,a,c，精确 distinct 状态若保存集合依次为 {a}、{a,b}、不变、{a,b,c}；小空间估计器则只更新哈希寄存器，无法列出原键。

若使用固定种子，可写作 $s_t=F(s_{t-1},a_t;r)$，流末由 $G(s_m)$ 解码。若每步抽取独立新币，则写作 $s_t=F(s_{t-1},a_t;r_t)$。这两种记法都必须说明随机性计费：输入无关、模型允许免费共享的只读种子可以作为公开参数；过去抽取而未来还会复用的私有种子，必须保存在工作状态内。

$S$-bit 状态指完整的可续跑配置，包括计数器、持久种子和必要的控制信息。在固定公开参数后，它至多有 $2^S$ 种取值。已耗用且不再访问的独立随机位不需要保存；若实现重新读取过去的随机带，所需带内容、种子或数据依赖的读取位置都要纳入可续跑配置并计费。这个区分使“状态限制历史信息”成为严格的资源约束，也保证状态交给另一方后能继续运行。

多趟模型允许第二趟重新读取 a,b,a,c，但跨趟保留的工作状态仍受空间限制。

概率量词和自适应性 ​

固定流保证先固定 $\sigma$，再对种子 $r$ 取概率。若系统公开每次估计，对手可根据误差选择下一键，最终流依赖 $r$；原保证不能直接条件化。隐藏种子、限制查询次数或采用抗自适应 sketch 是额外机制。

对固定合法流 $\sigma$，一种带误差尺度的保证是

取 $Scale(\sigma )=|F(\sigma )|$ 时，这是相对误差保证；使用其他尺度时，误差应按该尺度解释。

将失败率从常数降到 $\delta$ 常用 $O(\log \left(1/\delta \right))$ 个独立副本取中位数，空间和更新时间也同倍增加。不能只改定理中的概率而忽略资源。

通信下界接口 ​

通信下界归约公理库通信下界归约范式Communication lower-bound reduction pattern · Communication reduction for lower bounds用固定长度的 INDEX 编码，把单遍精确不同元素计数的完整内存状态变成一次消息，并逐项保留错误、随机性和空间单位。把流切成 Alice 前缀和 Bob 后缀。Alice 运行后只把 $S$-bit 状态发给 Bob，Bob 继续并解码；任何一趟 streaming 算法由此产生一个 $S$-bit 单向通信协议。用Indexing公理库Indexing 通信问题Indexing communication problem · INDEX problemAlice 持有 n-bit 串、Bob 持有索引并要恢复对应 bit 的单向通信问题，是流式与摘要空间下界的标准母问题。时，前缀通常编码 Alice 的位向量，Bob 的后缀和最终查询选择待恢复坐标；用Set Disjointness公理库Set Disjointness 通信问题Set Disjointness communication problem · DISJ communication problem判断双方私有集合是否没有共同元素的典型两方问题，其随机线性下界支撑大量空间与分布式下界。时，两段更新分别编码双方集合，使流输出能够判断是否存在交集。具体编码必须证明流合法并保存近似 gap，不能只因任务也涉及集合就套用下界。

若底层通信问题需要 $\mathrm{\Omega }(n)$ bits，且模拟没有额外消息，便排除对应流任务的次线性状态。多趟算法会在两方之间来回传递状态，对应多轮而非单向通信；随机种子是否公开、每趟起止方和最终输出位置也要与通信下界版本一致。

一个具体终点是宇宙 $[n]\times \{0,1\}$ 上的固定长度流：前缀依次为 $(j,x_j)$，末项为 $(i,1)$。不同元素数为 $n+1-x_i$，因此精确输出可以解码 INDEX 的第 $i$ 位，单遍最坏空间需要 $\mathrm{\Omega }(n)$ bits。完整编码与状态模拟公理库通信下界归约范式Communication lower-bound reduction pattern · Communication reduction for lower bounds用固定长度的 INDEX 编码，把单遍精确不同元素计数的完整内存状态变成一次消息，并逐项保留错误、随机性和空间单位。逐步证明了此结论，也说明本受限流族两遍只需 $O(\log n)$ bits：先记住末项，再重扫前缀检查它是否出现。遍数因此是定理前提，不能从空间符号中省略。

与在线和外存模型对照 ​

Online algorithm 强调未知未来下立即决策，可拥有线性记忆；external-memory 可反复随机访问磁盘，以 I/O 计费；streaming 主要限制 pass 与工作空间。三者都“顺序到达”时仍不能混用复杂度。