HyperLogLog：从概率计数到 Redis 实现的基数估计
12 KB 的 HyperLogLog 误差从哪来：沿 FM85、LogLog、HLL、HLL++ 到 Ertl 估计器推导，用 1000 次模拟实测各代估计器在小、中、大基数上的偏差，并对照 Redis 7.2.5 源码拆解稀疏/密集编码和三次更换的估计公式。
sketch 标签归档
共 3 篇文章 · 返回首页
t-digest：缩放函数、合并与尾部分位数误差
t-digest 用缩放函数限制质心大小，换来极小的尾部秩误差，但没有最坏情形保证。本文对照 Dunning 与 Ertl 预印本及 Elasticsearch、ClickHouse 源码，用可复现实验测量尾部误差与合并顺序的影响，并复现让误差达到约 40% 的困难分布。
流式算法总论：数据流模型、频率矩下界与线性 sketch
一遍扫描、内存远小于数据时能算什么：梳理三种流模型、Morris 到 AMS 与 Indyk 的谱系、通信复杂度下界，实测 AMS F2 sketch 误差随计数器数的变化，说明线性 sketch 为何可合并、可删除，并把本系列 30 到 35 篇串成路线图。