什么是Sketch？

[981377660LMT]

No description provided.

[981377660LMT]

https://zhuanlan.zhihu.com/p/521289977

[981377660LMT]

Sketch是概率数据结构的统称

[981377660LMT]

当面临海量数据时，完全存储这些数据几乎是不可能的，或者是没有必要的，因此，人们提出了一些概率数据结构，期望能用一个较少的空间来近似表示完整的数据集，在能够容忍误报的情况下，Sketch带来了空间和时间方面明显的性能提升，已被广泛地应用到许多应用场景

[981377660LMT]

在数据流分析或大规模数据处理的语境下，Sketch 是一种利用随机化和哈希思想来对大量数据进行紧凑表示（compressed representation）或近似统计的算法/数据结构。它能在只占用远小于原数据规模的空间的前提下，对数据的某些特征（如出现频率、基数、相似度、分布等）给出近似且可控误差的估计。

以下从几个方面来理解 Sketch 的本质：

---

1. 为什么需要 Sketch？

1.1 大数据场景的挑战

• 当数据量极为庞大（如社交网络日志、传感器数据流、点击流等），我们往往无力将所有数据都存储并在查询时完整扫描。
• 很多应用只需要对数据的某些统计特征（例如：出现次数、Top-K 频繁元素、数据分布、相似度度量、基数估计等等）做近似查询，而不必获取所有细节。
• 要在空间受限、实时性要求高的情况下完成统计分析，就需要在数据流（或大数据）到来时，动态地、在线地以极小的代价提取并维护关键信息。

1.2 随机化与近似的优势

• 与完全存储或完全精确计算相比，利用随机化思想可以在概率意义上控制碰撞和误差。
• 只要能保证“误差不超过某个阈值”或者“在 1−δ 的高概率下得到合理近似”，就能在工业/工程环境中足以应对大部分需求。

---

2. Sketch 的核心思路

2.1 哈希分桶

• Sketch 通常将数据通过哈希函数映射到一个规模较小的“空间”中；对于频率或分布的统计，往往在相应位置进行计数或标记。
• 哈希函数的好坏是决定 Sketch 质量的关键——需要“足够随机”且“可有效计算”，使得冲突或碰撞概率可分析、可控制。

2.2 多重哈希与碰撞削减

• 许多 Sketch（如 CountMin Sketch、Count Sketch 等）会使用多组独立（或近似独立）哈希函数，并在每组哈希对应的数组或计数器中记录一次。
• 查询时，通常取这些计数器中的某种聚合（例如 CountMin 的最小值）来得到最终估计。
• 多重哈希能在一定程度上减少单一哈希函数下可能出现的极端碰撞带来的误差。

2.3 子采样 / 指标变量

• 另一类 Sketch（如 HyperLogLog、Flajolet-Martin 等）通过哈希值的一些特征（如“尾部连续零的个数”或“最小哈希值”）来间接估计全局特征（如集合基数）。
• 这往往利用统计学的“无偏估计”思想：根据随机变量分布情况，设计出一个简单的观测（即“Sketch”）即可推断整体信息。

---

3. 常见的 Sketch 类型

3.1 CountMin Sketch

• 目的：近似记录每个元素的出现次数（Frequency）。
• 原理：用 (k) 个哈希函数和一个 (k \times w) 的计数表，将每个元素映射后加 1；查询时取各行对应列的计数器最小值作为频率估计。
• 特点：
  • 不会低估真实出现次数，可能高估，但有概率可控的误差上界。
  • 空间复杂度约为 (O(\frac{1}{\epsilon} \log \frac{1}{\delta}))，可在高概率下把误差控制在总数据量的 (\epsilon) 比例内。

3.2 Count Sketch

• 目的：同样用于频率统计，但允许正负计数（通过随机 (\pm1) 签名）。
• 优点：能在查询时更好地抵消碰撞带来的影响，尤其适合辨别频繁正贡献与负贡献并存的场景。

3.3 AMS Sketch（Alon, Matias, Szegedy）

• 目的：估计数据流的二阶矩（(\ell_2) norm）或其它高阶矩。
• 思路：基于随机投影 + 无偏估计原理，可以在子线性空间内近似计算数据流的“流量分布”特性，如方差、出现次数分布的平方和等。

3.4 HyperLogLog / Flajolet-Martin

• 目的：估计集合基数（Distinct Elements）。
• 方法：对元素进行哈希后，记录其哈希值中某一特征（如尾部零的最大长度或最右 1 的位置等），再通过预先推导的统计模型回推集合大小。
• 特征：在极小空间内（如几 KB）就能估计数以亿计的不同元素的基数，误差仍然保持在可控范围。

3.5 MinHash

• 目的：近似计算集合的相似度（如 Jaccard 相似度）。
• 方法：对每个集合都保留若干个最小哈希值，再通过最小哈希碰撞概率来估计集合交集/并集的比例。
• 典型应用：文档相似检测、相似推荐、重复内容检测等。

---

4. Sketch 的优点与局限

4.1 优点

1. 空间占用小：在大规模数据流分析中只需子线性（甚至常数）级别的空间。
2. 插入/更新效率高：每到来一个数据（或一条流记录），仅需几个哈希操作和简单的数组更新。
3. 误差可分析：通过概率论（Markov/Chernoff bounds 等），可给出较严格的误差上界和置信度。

4.2 局限

1. 只能得到近似结果：对于特定元素或统计量，Sketch 可能有一定误差。
2. 依赖随机哈希：需要选用合适的哈希函数，若哈希分布不均匀或出现过多碰撞，误差会变大。
3. 针对特定统计目标：一个 Sketch 通常对“频率”或“基数”或“相似度”等其中之一进行优化，不能一体通用。

---

5. 应用场景

1. 流式数据分析：网络流量监控、日志统计、点击流、传感器数据实时分析等，都能用 Sketch 减少内存占用和实时运算量。
2. 搜索与广告：快速估计关键词出现频率，决定是否投放广告，或进行频率上限控制等。
3. 大规模去重、基数估计：数据库查询优化、分布式计算中的 distinct count 问题，以及对集合相似度的快速估计。
4. 推荐系统：对用户-物品矩阵的大规模运算进行近似处理，如 MinHash+LSH 做相似度检索。

---

6. 小结

• Sketch 并不是单一的数据结构，而是一类基于随机化近似的技术集合，核心是：

  1. 通过哈希手段，将大规模数据映射到一个更小的表示空间。
  2. 通过统计和概率方法，保证估计误差可控。
  3. 在插入、查询上实现高效率和小空间占用的折中。

• 这些特性使得 Sketch 在现代大规模数据处理与流式计算中发挥着不可替代的作用。它们与采样、压缩感知、局部敏感哈希（LSH）、随机矩阵理论等一起，构成了大数据/流式分析领域最常用的核心工具箱。

---

总之，Sketch 的核心价值在于：

“用极小的存储与实时更新开销，在随机化的帮助下，对海量数据的某些全局统计量进行近似测度，并能提供明确的误差边界。”

这就是 Sketch 的本质与意义所在。