现有Sketch数据结构基本原理

写在前面

比较简略，偏差之类的理论推导建议去读论文，如果有误麻烦指出

套话由GPT生成

Sketch的基础是概要数据结构（Summary Data Structure），它是一种可以以较小的内存消耗来表示和估计大规模数据集的某些属性的数据结构。

概要数据结构通过对原始数据进行压缩、聚合或采样，以及使用一些统计方法和算法来近似表示数据的特征和属性。概要数据结构通过对数据进行摘要（summary）的方式，能够在有限的存储空间下提供对原始数据的近似信息。

哈希函数在Sketch中起着关键的作用，它用于将输入数据映射到Sketch数据结构的存储空间中。哈希函数将输入数据转换为固定长度的哈希值，这个哈希值用于确定数据在Sketch中的位置或索引。

通过使用哈希函数，Sketch可以将大规模的数据集映射到有限的存储空间中，从而实现对数据的压缩和摘要。哈希函数具有均匀性和随机性的特点，可以将数据均匀地分布到Sketch的存储空间中，避免冲突和数据集中。

Count-min Sketch

共\(d\) 行每一行都对应一个hash函数\(h_{i}\) ，每一行都具有\(w\)个计数器\(c_{ij}\)

UPDATE：对于第\(i\) 行，\(C_{ih_{i}(key)}+=1\)

QUERY：对于一共d行 返回\(min(c_{ih_{i}(key)})\)

特点：会有假阳性，因为结果是不小于实际值的估计

Reference：CORMODE G, MUTHUKRISHNAN S. An Improved Data Stream Summary: The Count-Min Sketch and its Applications[J].

Count Sketch

结构和Count-min Sketch相似，但多了\(d\) 个hash函数，选择\(d\) 个hash函数\(h_{i}->[w]\) 以及\(s_{i}->\){1,-1},两者成对独立

UPDATE：\(C_{ih_{i}(key)}+=s_{i}(key)\)

QUERY:返回 \(median(s_{i}(key)C_{ih_{i}(key)})\)

特点：假阳性和假阴性都有可能，甚至会出现负数，\(s_{i}\) 的设计为了抵消一些冲突项

Reference:CHARIKAR M, CHEN K, FARACH-COLTON M. Finding frequent items in data streams[J/OL]. Theoretical Computer Science, 2004, 312(1): 3-15.

HyperLogLog

实例观察网站：http://content.research.neustar.biz/blog/hll.html

图片来源：HyperLogLog 算法的原理讲解以及 Redis 是如何应用它的 - 指尖下的幽灵 - 博客园 (cnblogs.com)

UPDATE：对数据流进行hash后得到的值，假设低\(p\) 位指示桶号，剩下的位从低到高第\(i\) 个数出现第一个1，且指示的桶号中数值小于\(i\) ，则更新

QUERY：对所有的桶中的值求调和平均，LogLog算法直接求平均，代入公式，其中\(const\) 是修正因子，\(m\) 是桶的数量

特点：适用于大流量的基数估计，小流量容易出现较大偏差

Reference:FLAJOLET P, FUSY É, GANDOUET O, 等. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm[J/OL]. Discrete Mathematics & Theoretical Computer Science, 2007, DMTCS Proceedings vol. AH,...(Proceedings): 3545.