频率估计与 Heavy Hitter：Misra-Gries、Space-Saving 与空间下界
m 个计数器能把流中频率估到多准？核对 Misra-Gries、Lossy Counting、Space-Saving 的定理与两种下界，证明 MG 与 SS 同构，用 Zipf 流实测 top-100 召回与误差，对照 DataSketches、ClickHouse、RedisBloom 源码。
mergeable-summaries 标签归档
共 2 篇文章 · 返回首页
流式算法总论：数据流模型、频率矩下界与线性 sketch
一遍扫描、内存远小于数据时能算什么：梳理三种流模型、Morris 到 AMS 与 Indyk 的谱系、通信复杂度下界，实测 AMS F2 sketch 误差随计数器数的变化，说明线性 sketch 为何可合并、可删除，并把本系列 30 到 35 篇串成路线图。