数据流算法模型

资源协议 ​

流由更新 (a_1,\ldots,a_m) 顺序到达，算法通常一趟处理，只保留 (s\ll m) bits 状态；这是核心空间复杂度公理库空间复杂度Space complexity计算在输入长度函数下使用的工作存储单元数量。约束。任何算法都须报告 pass 数、update/query time 与空间口径。若算法使用随机摘要或近似输出，再另外说明误差尺度、成功概率及概率对哪些随机性取值；精确的确定性流算法并不需要这组参数。

网络包独立访客统计是例子：保存所有地址可精确计数但需线性空间；小摘要允许近似。把流写到磁盘再离线排序不属于小空间 streaming，尽管输入也按顺序读取。

一趟实例的状态演化 ​

处理同一包源地址流时，精确频率表、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$ bits，状态至多 $2^S$ 种；这既限制算法能区分的历史，也是后文通信下界的状态消息。

流末查询只运行解码器 $G(s_m)$；若要求每次更新后输出，就要把解码成本计入 worst-case update latency。多趟模型第二趟可重新读取 a,b,a,c，但工作空间仍受限；把它们写入自有日志则等价于使用线性外部空间，超出标准模型。

概率量词和自适应性 ​

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

对固定合法流 $\sigma$，一种完整相对误差陈述是

$${\text{Pr}}_r[|\hat{F}(\sigma )-F(\sigma )|\le \epsilon Scale(\sigma )]\ge 1-\delta .$$

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

通信下界接口 ​

通信下界归约公理库通信下界归约范式Communication lower-bound reduction pattern · Communication reduction for lower bounds将受限算法的执行切成双方可本地模拟的片段，把跨切口状态或访存内容变成消息并保留全部参数。把流切成 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，且模拟没有额外消息，便排除对应流任务的次线性状态。多趟算法会在两方之间来回传递状态，对应多轮而非单向通信；随机种子是否公开、每趟起止方和最终输出位置也要与通信下界版本一致。

与在线和外存模型对照 ​

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

参考资料

• Alon, Matias, Szegedy, “The Space Complexity of Approximating Frequency Moments,” JCSS, 1999.
• S. Muthukrishnan, Data Streams: Algorithms and Applications, 2005.