频数也可能减少
事件计数常常需要更正:删除重复记录、修改较早的数值,或把两个时段的频数向量相减。这些运算产生的坐标不一定非负。前一个 Count-Min 单元已解释,这时取最小值便失去“一定不会低估”的性质;与负坐标碰撞,可能把计数器拉到真值以下。
CountSketch 改变处理碰撞的方法。每个键除了桶编号,还有一个随机正负号。更新加入桶之前先乘上该键的符号,读取时再乘上被查询键的符号。符号的平方是一,所以目标键的贡献完整还原;其他键的贡献则可能为正,也可能为负。我们会证明它们的期望互相抵消,并用二阶矩衡量误差。
本单元证明的是指定键查询保证,不包含找出所有高频键的算法。
固定数据流与精确的正负计数器
定义 14.1.1
(净频数与一般 turnstile 模型)
设 为有限的键集合。一次更新 的键是 ,更新量 可为任意实数。在固定时刻 , 的净频数定义为
允许负更新量,而且允许净坐标为负,称为一般 turnstile(可增减)模型。
若要求每个坐标的净频数始终非负,则是较严格的 turnstile 模型;本篇证明不需要这项限制。完整的有限数据流要在摘要的随机选择以外固定。我们先处理也独立于这些随机选择的指定键 及时刻 。若输入本身随机,但与摘要独立,可以先对输入作条件化。
定义 14.1.2
(CountSketch 的各行与更新规则)
选择宽度 及奇数行数 。第 行选择桶函数 及符号函数 ,并要求:
- 不同键 满足 。
- 任意两个不同键的符号独立,而且每个符号均匀分布于 。
- 同一行的整个符号函数与整个桶函数独立。
- 不同行的函数对 互相独立。
所有计数器 由零开始。对更新 ,在每一行执行
第一项是通用哈希族的碰撞界,并不要求所有键的桶编号共同独立。下面的指定键二阶矩计算只需要两两独立的符号。使用一个确定性的哈希程序,或重复同一个种子,都不是上述性质的证明。
整个摘要生命周期内,符号及哈希函数保持不变。因此,一次更新及其精确相反数的效果会抵消。按更新次数作归纳可得,每一时刻都有
这是精确算术下的恒等式。用有界整数实现时要避免溢出,用浮点数时则需要另外分析舍入误差。
定义 14.1.3
(各行估计与中位数估计)
对被查询的键 ,各行估计及最后的指定键估计为
因为 是奇数,中位数就是排序后的中间一项。它容许少数行非常不准确。
概念视角代数
每一行都是一个随机线性映射
固定第 行并把键排序。令 为 矩阵,元素为 ;每一列恰有一个非零元素,等于 。计数器恒等式说:计数器数组的第 行就是 。此外
所以第 行对所有键的估计 等于 。对角元为一,而性质 2 与 3 使非对角元的均值为零,故 。下面的命题正是说:这个随机矩阵平均而言是单位矩阵,而每个坐标的离散程度受到控制。 的线性使兼容摘要可以相加相减;跨行取中位数是唯一的非线性步骤。
为什么每一行的平均估计正确
省略固定时刻的记号,写成
误差中没有目标坐标 。把其他坐标的平方质量记为
也就是删去被查询坐标后,剩余向量的欧几里得(Euclidean)长度平方。即使目标坐标很大,也不会把自己的碰撞误差界放大;其他大坐标才会影响这个界。正负净频数在平方和中不会互相抵消。
命题 14.1.4
(一次固定指定键查询的期望与方差)
在上述假设下,每一行都满足
期望针对随机函数而取;频数向量及被查询键均独立于这些函数而固定。
证明
(展开单行误差)
设 。两两独立的均匀符号给出 ,其中 。由于符号函数与桶函数独立,这个期望可与 的期望分开。因此 的每一项都是零,证得无偏性。
再展开误差平方。由 及 ,
对不同的 ,符号函数与桶函数独立,所以交叉项的期望可写为 。指示变量本身不必独立。对角项则由碰撞界至多为 ,故 。误差均值是零,所以这也是方差界。
证明透视
共同的查询符号先平方,才处理交叉项
各个误差项共用 ,不能直接说它们互相独立;证明其实不需要这样说。平方后,共同的符号变为 ,每个剩余交叉项只含两个不同符号,其乘积期望为零。这解释了为什么此处两两独立已足够。把符号部分和桶部分的期望分开,需要两个函数独立;不同行的独立性则稍后才用到。
命题说的是每一行,而非中位数;不能因为各行无偏,就直接宣称其中位数也保持期望。下一个证明会建立中位数的置信保证。
从方差界提高到高成功概率
若 ,其余坐标全为零,每一行的误差都恒为零,最后答案精确。以下设 。对 ,Chebyshev 不等式给出
选 ,每一行失败的概率便至多为 。增加桶数先降低单行失败概率,再用独立行进一步降低整体失败概率。
定理 14.1.5
(固定键及时刻的中位数置信保证)
设 。采用宽度 ,以及任意满足 的奇数行数 。对上述固定数据流、键及时刻,
这里的常数足够使用,而且刻意采取较保守的选择。
证明
(中位数失败需要过半数的坏行)
设 。若至少 个行估计落在 内,中间次序统计量也在此区间内。假如中位数低于区间,全部 个准确值都严格大于它,但排序后中位数后面只有 个位置,矛盾。高于区间的情况同理。因此,中位数失败必须有至少 行失败。
对任何预先指定的 行,行与行独立,所以它们全部失败的概率至多为 。若有至少 行失败,必然存在这样的一个集合。对 个可能集合用并集界,得
这里用了 ,以及 ;后者是因为全部子集共有 个。 的情况已是精确。证明完成,过程没有假设不同查询互相独立。
证明透视
为什么宽度常数取八而不是四
证明分为确定性和概率两部分。次序统计量这一步不用任何随机性:中位数失败必须有过半数的坏行。行之间的独立性只用来把某组指定的过半数行全坏的概率界为 ,其中 是单行的失败概率。并集界于是给出 ,只有当 时才会衰减。宽度取 时,Chebyshev 给出 ,所以任何 都可行;取 使 ,得到简洁的深度 。
摘要正好需要 个计数器,另加随机函数的描述。若 取最小允许奇数,计数器数目是 ;加一项反映即使 接近一,行数仍至少为一。一次更新接触 个计数器;一次查询读出 个值并找中位数。把值排序是一个简单做法,线性时间的选取方法则可避免完整排序。这些是运算量及计数器数目的界,并非固定的字节存储界。若更新是整数,而且已知更新量绝对值的总和为 ,每个计数器的绝对值至多为 ,故每个带符号计数器用 比特便足够。
包含低估的正负频数例子
例题 14.1.6
(先还原每行的符号,再取中位数)
设 。用三个桶,并考虑下表已实现的函数值。例如 代表桶零及符号负一。
| 键 | 净频数 | 第 1 行 | 第 2 行 | 第 3 行 |
|---|---|---|---|---|
| 5 | ||||
| -3 | ||||
| 2 | ||||
| 1 |
各行计数器是 、 及 。查询 时,乘回其符号后得到 ,中位数是 5。查询 时,各行估计是 ,中位数正是带负号的真值 。
对 ,碰撞误差的平方尺度是 。小表展示运算方法,不代表宽度三满足某个置信要求。取 、 时,上述充分定理要求宽度 128、行数 9,共 1152 个计数器;成功事件保证误差至多 ,约为 。
误差尺度是平方和,而非其余频数的带符号总和;下一个例子把两者的区别具体化。
例题 14.1.7
(相反的频数仍会进入误差尺度)
设被查询键 有 ,另外两个键有 及 。它们的带符号总和为零,但 ,故 。在一个已实现、满足 而 的行中,
虽然其余频数总和为零,该行误差的绝对值仍是 100,而且如尺度所预期,不超过 。由于 ,“误差至多 ”这个加性陈述仍有意义,除以 的相对误差却没有定义。因此定理并不是小坐标的相对误差保证。
常见错误
(读取桶值而忘记还原查询符号)
在上表中, 所在的桶值是 ,其中位数是 2。计数器存储的是 加上噪声,只有乘以 才能还原 。各行估计 的中位数是 5,正是准确值。
常见错误
(对带符号的各行取最小值)
在 Count-Min 中每次碰撞只加入非负量,所以每一行都高估,最小值是最安全的一行。有了符号,行误差可以为负,最小值会选中最负的一个。上表中 的最小值是 2,低估了 3,而中位数是准确的。
独立性的字句为什么不能省略
反例模式
符号的边际分布正确,仍不能把碰撞与符号绑在一起
取两个键 ,宽度二,并设 、。独立抽取均匀符号 。设 ;若两符号相同就设 ,否则设 。符号仍两两独立,碰撞概率也恰为 ,符合宽度二的要求;然而两个函数互相依赖。
符号相同时,查询 得到 2;符号不同时得到 0。两种情况各有概率 ,所以估计期望是 1,而非真值零。无偏性证明用到的一阶矩项 ,不能再分解为 。修正方法是把符号函数与桶函数独立抽取;分别检查两者的边际性质并不足够。
行与行的独立性,即性质 4,是另一项要求;多存几份副本并不能提供它。
常见错误
(复制一行而非重新抽取)
副本的失败事件与原行完全相同,复制九次仍保持同一个失败概率。中位数证明只可对独立构造的行把概率相乘;增加重复存储并没有增加独立信息。
线性合并、非线性查询与有限查询预算
分别摘要两个输入时,保留相同维度、哈希及符号。计数器恒等式对 是线性的,所以向量 的摘要逐项相加,恰为 的摘要;逐项相减则恰为 的摘要。如此就可比较两个固定时段,而不用保留每一个事件。合并前的输入向量仍须独立于随机函数。
对合并后的向量使用指定键定理。相减时,尺度是 。坐标抵消可能降低尺度,却不能单凭带符号总和为零就把尺度设成零。若两个摘要使用不同函数,逐项合并便没有上述恒等式。
例题 14.1.8
(中位数相减不等于查询差摘要)
假设两个兼容摘要对同一个键的三行估计分别是 及 。两者的中位数均为零,所以已返回中位数之差是零。逐行差为 ,其中位数是十。数组之差就是 的摘要,查询它才是合并向量保证所涵盖的运算;已返回中位数之差并没有这种保证,因为中位数是非线性的。
对独立固定数据流上 个预先指定的键与时刻配对,以上述宽度计算,每个配对失败的概率至多为 。并集界给出整体失败概率至多 ,所以任何满足 的奇数都足够。查询可以共用计数器,其误差不必互相独立。
若键集合大小是有限的 ,而已知有限时限 ,取 便可用同一事件保护所有键及截至 的每个前缀。在该事件上,读者可看过输出后才选查询,或选一个不超过 的停止时刻,因为所有可能的键与时刻已受保护。底层更新仍须独立于摘要而固定。这并不是针对依照输出选择未来更新的对手、无界时间或无限键集合的证明。
练习与完整解答
快速检查
(对算例的频数向量查询 ,改用宽度 20。求单行方差及绝对误差大于 2 的概率上界。前者必定等于真正方差吗?)
使用其余坐标的平方质量。
解答 · 答案
其余坐标的平方质量是 14,所以方差至多为 。Chebyshev 不等式把指定概率界为 。碰撞假设本身只是上界,故方差未必等于 0.7。这个计算不需要不同碰撞指示变量互相独立。
快速检查
(用本篇的充分构造,取 及整体失败预算 。对一次固定查询,求宽度、最小允许奇数行数及计数器数目;再对 16 次预先指定查询重算。)
多次查询时,在行数条件中以 代替 。
解答 · 答案
宽度为 。一次查询要求 ,故最小奇数为 7,共 224 个计数器。16 次查询要求 ,故取 15,共 480 个计数器。这是在分配同时失败的预算,并没有假设查询误差互相独立。
快速检查
(一个固定向量只有 非零。查询 必得什么结果?若改查询一个未出现的键 ,是否必定得到零?)
比较 与 。
解答 · 答案
对 ,每行都返回 ,所以中位数精确。对 ,碰撞会贡献 ,个别行估计可以非零,中位数也不保证对每次随机构造都为零。两个查询的尺度不同:,但 。近似答案非零,本身并不能证明该键曾出现。
快速检查
(在耦合哈希的反例中,把 改成任意固定实数 。计算查询 的期望,并指出究竟哪项假设失效。)
按两个符号是否相同分情况讨论。
解答 · 答案
符号相同时答案为 ,否则为零,所以期望是 。除非 ,否则估计有偏。符号仍两两独立且均匀,碰撞界仍为 ;失效的是整个符号函数与整个桶函数的独立性,因而不能作证明所需的期望分解。
快速检查
(两个时段各有键 一百次;键 在第一时段有 12 次,第二时段有 7 次。每次出现都是 更新,两个时段均无其他键出现。差向量是什么?兼容的差摘要查询 会返回什么?为什么不能据此在一般情况下直接把已返回的中位数相减?)
先把数组相减,再查询。
解答 · 答案
差向量的 坐标是 , 坐标是 。兼容数组逐项相减后,只剩下 非零,所以查询 时每一行都精确为 5。这个结论是在查询前先抵消坐标所得。一般而言,逐行差的中位数与中位数之差不同,前面的三行例子已展示这点,所以不能把相同论证移到后一种程序。
本单元完成的是正负指定键更新、精确数组恒等式、单行无偏性与方差、中位数置信保证,以及明确有限查询假设下的兼容线性合并。候选键搜索、删去多个大坐标后的更强误差界、对抗性自适应数据流及具体哈希族实现,仍未涵盖。