Count-Min Sketch
Count-Min Sketch 用多哈希函数估计频率，空间子线性但有过高估计，用于流数据频率统计。
用途
流数据频率近似统计，空间高效。
机制
d 行 w 列计数矩阵。更新 x：每行 i 对应位置 count[i][h_i(x)]+=1。查询 x：取 min_i count[i][h_i(x)]。过高估计概率 ≤we^(-d)，误差 ≤ε||f||_1。
用例
- 流数据统计
- 频率估计
- top-k 检测
Count-Min Sketch 用多哈希函数估计频率，空间子线性但有过高估计，用于流数据频率统计。
流数据频率近似统计，空间高效。
d 行 w 列计数矩阵。更新 x：每行 i 对应位置 count[i][h_i(x)]+=1。查询 x：取 min_i count[i][h_i(x)]。过高估计概率 ≤we^(-d)，误差 ≤ε||f||_1。