旧事件何时失效
累积总数回答的是“至今出现多少事件”,却不能回答“过去一小时出现多少事件”。如果我们已丢弃每个事件的时间,就不能在它过期时准确扣除。保存窗口内每一个比特可得到精确答案,但长度为 的窗口需要 比特。当可接受受控的相对误差时,摘要可以节省空间。
定义 17.1.1
(有效窗口与真实计数)
输入是在整数时刻到达的二元数据流 。固定整数 和 。处理完时刻 后,有效窗口由正整数时刻 组成,其真实计数为 。若 ,称时刻 的 1 在时刻 已过期。
即使输入为零,时间仍向前推进。以下保证对每条数据流都成立,无须随机输入、哈希或独立性假设。
桶与更新程序
定义 17.1.2
(桶摘要)
一个桶表示按时间排列的 1 事件中连续的一段;这些事件的时间不必连续。桶存储其大小(2 的幂)和其中最新的 1 的时间戳。桶摘要是一列桶:由旧至新,它们把尚未完全丢弃的 1 分成不重叠的段,而且桶大小不递增。
一个桶可以同时包含已过期与有效的 1,但只有最旧的保留桶可能跨越窗口边界。
时刻 的比特到达后,按次序执行:
- 丢弃最新时间戳不大于 的每个桶,因为其中所有事件已过期。
- 若 ,在末尾加入大小为 1、时间戳为 的桶;若为零则不加入。
- 当某个大小的桶超过 个时,选择其中最小的大小,合并该大小中最旧的两个桶。新桶大小加倍,时间戳取原先较新的时间戳。重复直至每种大小最多有 个桶。
相同大小的桶在不递增次序中排成连续的一段,因此选出的两个桶相邻。用其并集取代二者后,时间次序及大小不递增的性质仍然成立。每次合并减少一个桶,故循环终止。更新时先丢弃完全过期的桶;跨边界的桶仍有有效事件,必须保留。
查询时,加总最旧桶以外所有桶的大小;若最旧桶大小为 1,额外加 1,否则额外加它大小的一半。记结果为 ;没有桶时输出零。每个比最旧桶新的桶都完全在窗口内:它最旧的事件也比最旧保留桶中最新的事件更晚,而后者仍然有效。
定理 17.1.3
(确定性误差与空间界)
对每条二元数据流及每个时刻 ,上述估计满足
若 ,估计精确为零。最多存储 个桶。若运行至有限时刻 ,以绝对时间戳存储各桶所需空间为 比特。
证明
(同伴质量,然后误差与空间)
同伴质量。 大小 的桶,是在大小 的桶至少有 个时,合并其中最旧的两个而成。建立时,它后面至少还有 个同样大小的桶,共含至少 个 1。其后合并只改变分组,不会消除这些事件;只要该桶仍是最旧的保留桶,它最新的 1 仍有效,所有更晚的这些事件亦必然有效。因此无论后来如何分组,真实计数至少包含这些较新的事件。
误差。 若没有保留桶,所有曾存储的 1 均已过期;先前丢弃的桶在丢弃时亦已完全过期,所以 。若最旧桶大小为 1,其唯一事件有效,其他桶也全部有效,因此估计精确。否则设其大小为 ,其中 个 1 有效。最新事件有效,所以 。其他桶均被精确计数,故绝对误差为 。上面的同伴论证给出 ,故 ,从而得到相对误差界。
空间。 若最旧桶大小 ,它后面的同伴都在长度为 的窗口内,因此 ,亦即 。其余桶不比它大,故所有桶的大小均不超过 。大小是由 1 起的 2 的幂,可能种类最多为 ,每种最多有 个桶,证得桶数界。有限运行至 时,绝对时间戳需要 比特,已存储桶的大小亦可用同阶比特表示。此结论不计外部输入的存储,也不声称每次更新的最坏时间是常数。
证明透视
合并规则为最旧桶的不确定性买单
估计中唯一的不确定之处,是最旧桶有多少个 1 仍有效;较新的桶都被精确计数。所以证明只需要一条不等式:用最旧大小 给真实计数一个下界,而合并规则正好提供它。规则有两处被用到。只在某大小超过 个时才合并,保证建立时仍剩 个同大小的桶。合并的是最旧的两个,保证这些剩下的桶较新,所以只要合并所得的桶仍被保留,它们就仍然有效。过期条件通过最新时间戳进入:保留的桶有一个有效的最新事件,这给出 ,并把同伴留在窗口内。空间界把同一不等式与窗口长度比较,得 ;误差与内存都由同一个计数事实控制。
第一个例子在一段短输入上追踪更新规则,其中包括一次过期。
例题 17.1.4
(过期与半桶估计)
取 、,连续输入六个 1。时刻 1、2、3 过后,时间 1 和 2 的单例桶合并,状态是 ;每对数字表示(大小,最新时间戳)。时刻 4 的状态是 。时刻 5 合并最旧的两个单例,得到 。时刻 6 的截止点为 ,故丢弃最新时间戳为 2 的桶,得到 。估计为 ,但时刻 3 至 6 的真实计数为 4;误差 1 小于一般界 。这个例子中最旧保留桶恰巧全在窗口内,但单凭其最新时间戳无法知道这点。
例题 17.1.5
(连锁合并及其同伴)
取 、,连续输入七个 1。如上,时刻 5 后的状态是 ,时刻 6 加入 。时刻 7 的截止点为 ,没有桶过期。加入 后有三个单例,于是 合并为 。此时大小 2 有三个桶 ,最旧两个合并为 。最终状态为 。桶 建立时有 个较新的大小 2 同伴,即 ,其质量为 。估计为 ,真实计数为 ;误差 不超过 ,也不超过 。
例题 17.1.6
(边界情形:所有 1 都过期)
取 、,输入 。时刻 2 后的状态是 。时刻 3 的截止点为 ,丢弃 ,剩下 ;估计 等于 。时刻 4 的截止点为 , 也被丢弃。摘要为空,输出零,正好等于 ,符合定理要求。两个零没有建立任何桶,却各自使截止点前进。
反例模式
最新时间戳不能告诉我们边界如何切分
取 、,比较到时刻 6 的历史 和 。两者摘要都是 :第一条数据流的大小 2 桶包含时刻 3、4,第二条则包含时刻 2、4。但窗口计数分别是 3 和 2,所以同一摘要不能同时给出两者的精确答案。把每个保留桶全部计入会高估第二个历史。
常见错误
(只在 1 到达时才执行过期步骤)
零不建立桶,但仍推进时间,而过期取决于时间。若实现只在 时丢弃桶,上面边界情形的例子在时刻 4 后仍保留 两个桶,回答 而不是 。丢弃步骤必须在每个时刻都执行。
如何使用这个界
增加 可改善已证明的相对误差界,但会增加存储量。若要求 的相对误差,取 便足以保证误差不超过 ;这是充分选择,并非最优性的证明。方法估计的是 1 的个数,并非任意带符号或加权数值的总和。它把到达次序当成事件时间;迟到事件和删除任意过往事件需要另一套约定。重复到达会被计算两次;若不同摘要的事件重叠,也不能直接把估计相加。
此界有意保守:即使最旧桶完全在窗口内,只要其大小大于 1,我们仍只计一半。额外存储最旧时间戳可辨认部分完全有效的桶,但一般仍不能确定有多少内部事件跨过边界。
常见错误
(把半桶估计读成对切分的断言)
半桶估计是利用现有信息所得的保证,并非假设实际恰有一半事件过期。在第一个例子中,最旧桶完全有效,却被计为 而不是 。保证针对的是所有具有相同摘要的历史中的最坏情形。
练习与解答
快速检查
(取 、,输入 。列出时刻 4 的桶与估计。)
加入新桶前先检查截止点 。
解答 · 答案
时刻 3 的状态为 。时刻 4 的截止点为 1,没有桶过期;加入 后得到 。估计为 ,真实计数也是 3。
快速检查
(取 、,输入 。求时刻 6 的状态和计数。)
零仍会移动截止点。
解答 · 答案
时刻 5 的截止点为 2,丢弃 ,剩下 。时刻 6 的截止点为 3,丢弃 ,剩下 ;估计及真实计数均为 1。零不建立桶,但仍使截止点前进。
快速检查
(若要保证相对误差不超过 ,当 时,给出可用的 和桶数界。)
用 及定理中的桶数界。
解答 · 答案
取 ,因为 。由 ,定理给出最多 个桶。这只是上界,并非声称所有桶可同时出现。
快速检查
(若最新时间戳等于 的桶仍被保留,为何违反上述更新规则?将其全部计入可能有何问题?)
与窗口定义中的严格不等式比较。
解答 · 答案
有效时间满足严格不等式 ,该桶所有事件均已过期;全部计入会包含旧事件。例如 时,时刻 1 的唯一一个 1 在时刻 2 已不应计入。
快速检查
(若实现改为合并两个最新的同大小桶,哪一步证明失效?)
看同伴相对于合并所得桶的位置。
解答 · 答案
合并后未必有 个同大小桶在新桶之后。较旧的同伴可能在新桶仍有效时过期,所以不能再推出有效的较新事件数量下界。这只说明需要另一个证明,并未确定替代算法的实际误差。