动机
数据流中的更新数量可能远超能够逐条存储的规模。如果元素全集很大,为每一个可能的元素维护一个精确计数器同样代价高昂。Count–Min 草图使用一个由若干共享计数器组成的小数组。当更新均为非负时,哈希碰撞只会使估计值增大;而多行相互独立的计数器使得较大的高估变得不太可能发生。
该保证是相对于数据流总权重的加性误差,并不是对每个稀有元素都成立的相对误差保证。我们先对一个固定的查询以及一个独立于草图随机哈希而选定的更新流证明结果,然后说明如何对有限个查询得到同时成立的保证。
定义
设 为有限的元素全集。数据流由若干更新 组成,其中 ,增量 为非负整数。设 为元素 收到的增量总和,并设 为数据流的总权重。计数均为精确的非负整数;零增量无害。
选取宽度 与深度 。对每一行 ,从满足下列条件的哈希函数族中随机选取哈希函数 :
各行相互独立。这一碰撞性质可由均匀的两两独立哈希值推出,但证明只需要每一行内部所显示的碰撞概率界。我们假定所述函数族可以被抽样并求值;它的表示方式与计算代价属于另外的实现要求。
维护计数器 ,初始为零。收到更新 时,在每一行中把 加到 上。对于查询元素 ,返回
定理
定理 10.2.1
(固定查询的 Count–Min 保证)
对 与 ,取 与 。对任意固定的非负数据流与固定的查询 (二者均独立于哈希函数),有
定理 10.2.2
(有限个查询的同时保证)
对于固定的、含 个查询元素的集合 ,取深度 ,则它们的所有估计值以至少 的概率同时满足相同的加性误差界。
证明:单行
证明
(单行的误差)
固定 与某一行。该行中被查询的计数器包含对 的全部更新,以及对与 发生碰撞的其他元素的更新。定义非负的碰撞噪声
于是 。由于增量非负,这一不等式对每一种哈希结果都成立。对各行取最小值同样不会产生低估。
由期望的线性性与碰撞概率界,
对不同的 ,其碰撞指示变量不必相互独立;只需要各自的概率以及线性性即可。若 ,马尔可夫(Markov)不等式给出
若把严格不等号换成非严格的阈值,同样的界仍然成立。若 ,则所有计数器与真实频率均为零,结论显然成立,无需在零阈值处应用马尔可夫不等式。
证明:独立的行与查询
证明
(对行与查询的放大)
对固定的数据流与查询,第 行的噪声只取决于该行的哈希函数。各行相互独立,因此“各行噪声超过 ”这些事件相互独立。仅当每一行的噪声都过大时,最小估计值才会超过 。其概率至多为 。再结合确定性的“不会低估”性质,即证明了固定查询的界。
对于固定的 个查询元素,在逐个查询的计算中把 换成 。所选的深度使得每个查询失败的概率至多为 。由并集界,任一查询失败的概率至多为 。各查询的失败事件可以相互依赖;并集界并不要求它们之间独立。
证明透视
概率的两种用法
各假设用在哪里:增量非负给出确定性的 ,并使 非负,从而可用马尔可夫不等式。碰撞界只通过期望的线性性使用,所以 不需要碰撞项之间相互独立。关键一步分两层:马尔可夫不等式把均值化为单行的常数失败概率 ,独立的各行再把它提升到 次幂。对多个查询,用并集界代替独立性,所以深度只随 对数增长。若流或查询是在看到哈希之后才选定,“流与查询固定”的前提便不成立,论证不再适用。
例题详解
例题 10.2.3
(一次碰撞)
设数据流的频率为 、,且某一行把 与 哈希到同一个桶。该行中 被查询的计数器为七,故其碰撞噪声为三。另一行把二者分开,其计数器为四,两行计数器的最小值即为精确频率四。
例题 10.2.4
(零数据流)
若所有增量均为零,则 ,且每个计数器保持为零。每个查询都返回其真实频率零。此时无需除以 。
例题 10.2.5
(选取维度)
取 与 ,按所述取法得 ,。对固定的查询,加性误差大于 的概率至多为 。这是对固定数据流的最坏情形界,并不是说典型误差就等于 。
例题 10.2.6
(稀有元素)
若 、 且 ,则该保证允许估计值高达 。相对于 而言这是较小的加性误差,但对 本身却是很大的相对误差。该定理对稀有元素不提供任何乘性保证。
常见错误
反例模式
负更新会破坏单侧性
设 ,另有一个元素 对与 共享的桶贡献了 的负更新。该行计数器可能为 ,低于 的真实频率。取最小值无法修复所声称的确定性下界。该定理假设增量非负。
常见错误
(把固定输入的保证用于自适应的流)
概率陈述要求数据流与查询的选取独立于随机哈希。如果对手能够检查草图,并根据哈希结果选择后续更新或查询,则上述针对固定输入的计算并不会自动适用。自适应情形的保证需要另外的模型与证明。
常见错误
(用平均值代替最小值)
取最小值对放大论证至关重要:只要至少有一行的碰撞噪声较小,最小值就较小。对计数器取平均则是另一种估计量,需要另行分析。
概念视角代数
草图是频率向量的线性像
设 为频率向量。计数器满足 ,其中 是 - 矩阵,每个行块的每一列恰有一个 ,位于桶 。因此两个数据流合并后的草图等于它们草图之和,而 中的第二项正是碰撞噪声。
空间与更新代价
草图存储 个整数计数器。每次更新计算 个哈希并递增 个计数器;每次查询计算 个哈希并取最小值。在常数时间哈希与字长计数器运算的假设下,每次更新或查询需要 时间。如果计数可能超过一个机器字,则必须计入其位长与算术代价。哈希函数的描述同样占用空间,对具体的函数族必须一并计算。
按所给参数取法,,,因此共有 个计数器。这是计数器的个数,并不自动等于相同数量的比特。在非负数据流模型中,每个计数器必须能表示至多 的数值。
具体实现必须使用具有所述概率的碰撞函数族、相互独立的各行选择,以及与全集相容的表示方式。由完全独立的哈希值构成的理想化表在数学上有效,但可能需要与 成正比的空间。该定理把草图分析与这一构造代价分开处理。
有限设定下的一个具体碰撞函数族
设全集是有限域 ( 为素数)的子集,并取草图宽度恰为 。从 中独立且均匀地选取 ,定义域中的 ,并把其 个值与桶标签等同起来。对于互异的 ,发生碰撞意味着 。由于域中 ,这恰好在 时发生,概率为 。
事实上,这两个哈希值是联合均匀的。对任意给定的输出 ,方程 与 有唯一解:,。因此,在等可能的 种 取法中,每个输出对恰好出现一次。对每一行独立地选取这两个域元素,便得到相互独立的各行函数。
这一构造说明了该假设如何成立,但它并不是一般的压缩全集方案:它要求把 单射地表示到大小为 的域中,并使用 个桶。特别地,若 ,所得宽度可能过大,以致相比精确计数器并不节省空间。更小宽度的实用函数族需要自行证明所需的碰撞概率界;简单地把域中的值对一个无关的桶数取模可能引入偏差。
跟踪计数器
考虑宽度为三的两行草图。设第一行把 哈希到桶 ,第二行把它们哈希到 。依次处理更新 、 与 。第一行计数器变为 ,第二行计数器变为 。查询 时读到五与二,返回二,即其精确频率。查询 时读到五与七,返回五,比真实值三高估了二。查询 时读到四与七,返回四,即其精确频率。只要另一行把被查询的元素与和它碰撞的元素分开,某一行中的碰撞就不一定导致最小值出错。
这个例子区分了某个具体的哈希结果与概率保证。该定理并不保证每一种哈希选择都给出小误差;它界定的是:对固定的数据流与查询,在所述的随机行选择之下,出现大误差的概率。对于这个小例子的宽度与深度,我们并未断言任何具体的数值失败概率保证。
马尔可夫不等式的推导与使用
对非负随机变量 与 ,逐点不等式 给出 。整理即证明马尔可夫不等式。这里由于更新非负, 非负,故该论证适用于碰撞噪声。总权重为零的特殊情形直接处理,因为此时阈值 为零。
该定理界定的是 。如果估计值恰好等于上边界,它仍然满足保证。即使 不是整数,在马尔可夫不等式中使用非严格阈值,也能为严格失败事件给出有效的上界。
对于预先确定的 个查询,并集界控制了其中任何一个失败的事件。该集合可以取为整个有限全集,当 非空时代价是深度取 。这一同时保证在同一个高概率事件上对所有这些元素成立。它并不自动涵盖在观察草图之后改变数据流的、无界的自适应更新序列。
解读参数的权衡
增大宽度会降低每一行的期望碰撞噪声;增大深度会降低每一行都出现大碰撞的概率。这两种效应出现在证明的不同部分。如果不控制单行噪声而只把深度加倍,并不能由此单独建立所述阈值;而只加宽单独一行,也不会产生同样的指数式置信度放大。
常数 与取整的选择只是方便的充分取值。只要 ,其他的宽度与深度可以直接依据界 来分析。使用不同的常数可能改变数值上的空间界,但证明结构保持不变。参数公式中的所有对数均为自然对数。
总结
一行计数器等于真实频率加上非负的碰撞噪声。碰撞性质界定了期望噪声,马尔可夫不等式界定单行的失败概率,而相互独立的各行则放大了“至少有一行准确”的概率。并集界把结果推广到任意固定的有限查询集合。
练习
快速检查
(为什么在更新非负时,估计值永远不会低于真实频率?)
每一行在真实频率之上加了什么量?
解答 · 答案
每个被查询的计数器包含对被查询元素的全部更新,加上来自碰撞元素的非负贡献。一组都至少为 的数的最小值仍然至少为 。
快速检查
(若某一行的期望碰撞噪声至多为 ,当 时,马尔可夫不等式对噪声超过 给出什么界?)
对碰撞噪声应用马尔可夫不等式。
解答 · 答案
至多为 。
快速检查
(为什么在所给出的指数式失败概率计算中需要各行之间相互独立?)
各行的失败概率是如何合并的?
解答 · 答案
证明把“每一行噪声都过大”的概率相乘。对于固定的数据流与查询,这一相乘由各行哈希函数相互独立来保证;相关的各行可能同时失败。
快速检查
(对于 个固定查询,要使总失败概率至多为 ,应如何选取每个查询的失败概率预算?)
把总失败预算分配给各查询。
解答 · 答案
对每个查询使用至多 的失败概率。由并集界,总失败概率至多为 。