Filtering and sampling streams - CS 591 K1: Data Stream Processing and Analytics Spring 2020

• 语言: 英语
• 格式: .pdf
• 来源: vasia.github.io

摘要

文档讨论了数据流处理中的抽样和过滤技术，重点介绍了抽样方法（synopsis）的使用及其优势和局限性。抽样是一种高效的处理方法，适用于大规模数据流和高吞吐量场景，能够提供近似结果并支持多种查询需求。文档还详细介绍了reservoir sampling算法，该算法通过固定大小的样本集S，确保每个元素以s/n的概率被选中，其中s是样本大小，n是已看到的元素总数。抽样的主要缺点包括对高度选择性查询的不适用性、对偏斜和异常值的敏感性以及某些查询类型难以找到合适估计器的问题。

AI总结

文档内容主要介绍了数据流处理中的抽样和过滤技术，重点讨论了如何通过维护简洁的摘要（synopsis）来高效处理大规模数据流或快速数据流。以下是核心观点和关键信息的总结：

1. **摘要的作用**
- 摘要是一种有损压缩的总结，用于替代直接在原始数据集上执行查询。
- 维护摘要通常是唯一能够在探索大规模数据集或高速数据流时提供交互式响应时间的方法。
- 用户查询是基于摘要而不是整个数据集执行的。

2. **抽样的优势**
- 简单易懂且易于实现。
- 有近100年的抽样研究可以借鉴。
- 抽样可以在线适应查询需求：
- 如果小样本无法提供足够的准确性，可以动态增加样本量。
- 抽样是一种通用的摘要方法，适用于回答多种任意查询。

3. **水库抽样（Reservoir Sampling）**
- 方法：
1. 将前s个元素添加到样本集合S中。
2. 当第n个元素（n > s）到达时，以概率p = s/n选择是否将其加入S。
3. 如果被选中，则随机选择S中的一个元素替换为新元素。
- 声明：在时间tₙ时，每个元素出现在S中的概率为s/n。

4. **抽样的局限性**
- 对于仅依赖少数元组的高选择性查询，抽样可能不适用。
- 在某些情况下，使用抽样进行估计可能比其他方法（如直方图）更耗时。
- 抽样通常对数据偏斜和异常值敏感。
- 难以找到适用于某些查询（如NOT IN、DISTINCT、外连接等）的良好估计器。

5. **无界流的抽样方法**
- 目标：维护一个固定大小的样本S，使得每个元素出现在S中的概率为s/n。
- 方法：
- 固定存储样本大小s，动态调整样本内容以保持代表性。
- 适用于实时处理无界数据流，同时支持未知的任意查询。

总结而言，抽样是一种高效的数据流处理技术，但在特定场景下可能存在局限性，需要结合其他方法（如更紧凑的摘要）来优化性能。