MMD_3b_StreamAlgorithms
MMD_3b_StreamAlgorithms
- Stream概述
- DBMS的区别
- Stream模型
- Query种类
- 应用
- Sliding Windows
- 简介
- 例子
- Bloom Filter
- motivation
- Continued
- LookUp
- Performance
- Sampling a Stream
- motivation
- 原因与解决
- 其他
“Streams” are data inputs to a system that arrive at a very high rate,typically too fast to do anything significant with each arriving input. Examples include data beamed down from a satellite, or click streams for a en necessary to accept a less-than-accurate answer to questions such as “how is stream?” .
Stream概述
遇到的主要问题是：同一时刻来的数据太多，一方面来不及存储到DB中，另一方面来不及处理和计算。 所以，问题的核心是抽样，不必先保存所有stream在计算。
一方面，可以实时计算，老的就扔了，比如sliding window；另一方面，可以对stream抽样，选取研究的关键变量，减少数据量。
DBMS的区别
Stream模型
Query种类
应用
Sliding Windows
就像一个滑窗，每进来一个数据只计算当前数据，不需要重复计算之前的数据，增快了速度。
简介
例子
Bloom Filter
motivation
与sliding window的区别，不仅仅只看一个window，而是关心整个stream.
爬虫的时候，已经爬过的URL需要放在一个list中。这样当新的URL进入时，判断是否已经爬过。
但是，当list中的URL很多的时候，查询相当费时间O(N∗M)O(N*M)。 即使用HASH-TABLE，只能减少单个URL查询的时间，但是返回的URL很多，这样还是很消耗时间的。
所以，需要一定的手段对URL进行过滤。
Continued
LookUp
Performance
把positive定义为list中已经存在的url。
那么，Bloom Filter会有一定的false positive，即把没有看过的url当成看过的，但是整个问题不大，因为重要的网页一般会有很多url指向它，所以不必担心单个url的遗漏问题。
同时，他没有 false negtive，即不会把看过的当成没看过，这样就可以保证爬虫的效率，不会重复爬相同的url。
false positive的概率与bit的个数还有hash function的个数有关。
试想，如果1的比率很高的话，那么false positive的概率变回很大。因此，增大bit的个数和hash-function的个数，可以有效地减少false positive。
Sampling a Stream
motivation
简单的random sample无法完成对于unique query fraction的查询，往往会高估了这个值。
原因与解决
其他
