滑动窗口流模型

窗口左边界不断推进，但小空间摘要通常已经忘记最旧的单项身份。可行方法把历史压成带时间范围的桶或后缀锚点：边界之外的整段直接丢弃，边界之内的整段完整保留，只让极少数跨界摘要承担可控误差。

图展示下述规则在 $K=1$ 时的一种桶形状：最旧桶跨界，其余桶完全有效。要求更小的误差时，每个级别需要保留更多桶。

Exponential Histogram ​

以最近 $W\ge 1$ 位中的 1 计数为例，取 $0<\epsilon \le 1$、$K=\lceil 1/\epsilon \rceil$。Exponential Histogram 把按到达顺序相邻的 1 聚成桶，每桶保存其大小和最新一项的序号。大小均为二次幂，每种大小最多保留 $K+1$ 桶；新 1 先建一个单项桶，某级达到 $K+2$ 桶时合并该级最旧的两个，大小相加，时间戳取两者中较新的一个，并继续处理进位。每次到达后，删除最新序号已经不大于 $t-W$ 的桶。

桶按时间排列且互不交错，所以剩下的桶中至多只有最旧桶跨越窗口左边界。设其大小为 $B$，所有较新桶的总大小为 $A$。无桶时返回零；$B=1$ 时最旧桶也完全有效，返回 $A+1$；$B\ge 2$ 时返回 $A+B/2$。真实窗口计数 $T$ 在 $[A+1,A+B]$ 内，故绝对误差至多 $B/2$。

误差界来自桶数量的下界，而不只是“桶数不多”。一个大小为 $B\ge 2$ 的桶形成后，每个更小级别至少留下 $K$ 个较新桶；该桶仍在时，这些较新级别不会先过期。后续同级合并又把数量从 $K+2$ 降至 $K$，因而该下界保持。于是

从而 $|\hat{T}-T|\le B/2\le T/K\le \epsilon T$。这给出了一个略保守、参数明确的相对误差版本。

每级只有 $O(K)$ 个桶，共 $O(\log (W+1))$ 级，因此使用 $O(K\log (W+1))$ 桶。时间戳可按窗口尺度循环编码；连同桶大小，总空间为 $O(K{\log }^2(W+1))$ 位。这里假设计数窗口固定，编码能区分当前窗口内外的序号。

例如 $W=8$，1 出现在序号 $1,2,4,5,8,9$。到序号 9 时有效范围是 $2\dots 9$，真实计数为 5。若 $\epsilon =1/2$，则 $K=2$；按上述规则，最终桶从旧到新为 $\{1,2\}$、$\{4,5\}$、$\{8\}$、$\{9\}$，大小为 $2,2,1,1$，最新时间戳为 $2,5,8,9$。最旧桶跨界，其余桶贡献 4，半桶估计再加 1，恰得 5。

Smooth Histogram 框架 ​

对满足平滑性条件的非负函数 $f$，Smooth Histogram 保存一串递增起点

及各后缀 $t_i\dots t$ 的流摘要。若相邻后缀的函数值过于接近，就删除中间锚点；新更新到达时扩展所有保留摘要，保留窗口起点两侧所需的相邻锚点，并淘汰更老、已不再用于夹住边界的锚点。

查询选择夹住真实窗口起点的两个锚点，利用函数的平滑性把较长后缀的近似转成窗口近似。这里需要函数级定理，不能仅因摘要“可合并”就断言它支持删除任意前缀。

最近一小时 distinct count ​

网站以事件时间统计最近一小时独立用户。系统可在若干锚点维护 distinct sketch：10:00、10:20、10:35、10:47 等后缀摘要随新用户 ID 更新。当查询时刻从 11:00 推进到 11:08，真实窗口起点从 10:00 移到 10:08。起于 10:00 的后缀仍包含大量窗口内事件，因此不能因为起点过期就立即整份丢弃；10:00 与 10:20 两个后缀夹住真实起点，是否能据此给出所需近似，要由所选函数及摘要的窗口定理保证。

若使用 HyperLogLog 等摘要，合并寄存器可以组合不相交时间段，但不能从“截至现在”的寄存器中减去 10:00 前的用户。锚点框架负责过期语义，distinct sketch 负责每个后缀的集合基数估计；两者的误差和失败概率要共同配置。

同一用户在多个时间段重复出现不会给并集增加新元素。这也是不能用各桶 distinct 估计值直接相加的原因；必须合并能够处理重复的摘要状态，或采用为窗口 distinct 专门证明的结构。

乱序时间戳 ​

若输入按事件时间有序，过期判断只需比较队首时间。真实系统常允许迟到 $L$：若系统保证每个事件最迟在其时间戳之后 $L$ 时间单位到达，可在处理时钟 $\tau$ 将 watermark 设为 $\tau -L$，表示该界之前的事件应已全部到齐，并在 watermark 推进时关闭旧桶。

晚于容忍范围才到达的事件必须有明确策略：丢弃、修正历史结果，或触发重算。把处理时间窗口写成事件时间窗口，却没有 watermark 和迟到规则，会使同一输入因网络调度不同而产生不同含义。

边界与对照 ​

滑动窗口不同于 turnstile 流。后者由输入显式给出正负更新，算法看到删除的是哪个键；窗口模型的删除由位置或时钟自动触发，键可能早已被压缩掉。它也不同于保存最后 $W$ 项的普通队列，后者精确但空间线性。

窗口大小若小于一个桶、查询时间倒退、时间戳重复或窗口突然改长，都需要接口约定。经典算法通常假设窗口参数固定且查询时钟单调；动态扩大的窗口无法恢复已经丢弃的历史。