MMD_3b_StreamAlgorithms

“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的查询,往往会高估了这个值。

原因与解决

其他

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏章鱼的慢慢技术路

通过C#脚本实现旋转的立方体

1824
来自专栏章鱼的慢慢技术路

通过C#脚本实现旋转的立方体

1173
来自专栏Android点滴积累

Android高效内存之让你的图片省内存

Android高效内存之让你的图片省内存        在做内存优化的时候,我们发现除了解决内存泄露问题,剩下的就只有想办法减少真实的内存占用。而在App中,大...

19611
来自专栏深度学习之tensorflow实战篇

R语言之系统聚类(层次)分析之图谱形式完整版

读取数据常见错误: 在读取数据过程中可能遇到以下问题,参照上一篇博客: 可能遇到报错: 1、Error in if (is.na(n) || n > 65536...

4145
来自专栏AI派

TensorFlow修炼之道(3)——计算图和会话(Graph&Session)

在计算图中,节点表示计算单位,边表示计算用到和产生的数据。 例如,在TensorFlow图中,tf.matmul操作将对应于具有两个输入边(要乘以的矩阵)和一个...

2894
来自专栏漫漫深度学习路

pytorch学习笔记(七):pytorch hook 和 关于pytorch backward过程的理解

pytorch 的 hook 机制 在看pytorch官方文档的时候,发现在nn.Module部分和Variable部分均有hook的身影。感到很神奇,因为在使...

4735
来自专栏Golang语言社区

转--每周一个GoLang设计模式之组合模式

GoF在第二章通过设计一个Lexi的文档编辑器来介绍设计模式的使用,GoF认为Lexi设计面临七个问题: 1. **文档结构**2. **格式化**3. **修...

2786
来自专栏CDA数据分析师

36条常用Excel技巧 收藏备用!

1、两列数据查找相同值对应的位置 =MATCH(B1,A:A,0) 2、已知公式得结果 定义名称=EVALUATE(Sheet1!C1) 已知结果得公式 定义名...

1795
来自专栏视觉求索无尽也

Markdown:插入数学公式

1001
来自专栏杨熹的专栏

几种简单的文本数据预处理方法

本文将介绍几种简单的文本数据预处理方法,希望与大家共同学习分享。

2934

扫码关注云+社区