Count-Min Sketch：点查询误差界、保守更新与生产实现
Count-Min Sketch 的误差是 εN 的加性界而非相对误差。本文核对原论文定理条件，用 Zipf 实验比较标准更新、保守更新、count-mean-min 与 Count Sketch，并对照 RedisBloom、DataSketches、Caffeine 源码。
datasketches 标签归档
共 2 篇文章 · 返回首页
频率估计与 Heavy Hitter：Misra-Gries、Space-Saving 与空间下界
m 个计数器能把流中频率估到多准？核对 Misra-Gries、Lossy Counting、Space-Saving 的定理与两种下界，证明 MG 与 SS 同构，用 Zipf 流实测 top-100 召回与误差，对照 DataSketches、ClickHouse、RedisBloom 源码。