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 条评论
登录 后参与评论

相关文章

来自专栏简书专栏

基于jieba、TfidfVectorizer、LogisticRegression的垃圾邮件分类

jieba中文叫做结巴,是一款中文分词工具,官方文档链接:https://github.com/fxsjy/jieba TfidfVectorizer中文叫做...

1191
来自专栏技术专栏

Spark SQL/Hive调优

任务进度长时间维持在99%(或100%),查看任务监控页面,发现只有少量(1个或几个)reduce子任务未完成。因为其处理的数据量和其他reduce差异过大。 ...

2742
来自专栏李海辰的专栏

Unity 引擎资源管理代码分析 ( 1 )

目前网络上已经有很多介绍 Unity 资源管理机制、和 API 使用方法的文章,但少有文章从 Unity源码层面对其实现进行深度解析。作为一名喜欢打破砂锅璺到底...

8431
来自专栏和蔼的张星的图像处理专栏

DSP图像处理

最近着手把CSK移植到DSP中,先看一些DSP中图像处理的一些例子,第一件事当然就是怎么把图像数据倒入CCS工程中了,去年倒是用过一点CCS,再拿起来已经忘得差...

1422
来自专栏编程札记

Spark的分区机制的应用及PageRank算法的实现

Spark中有一个很重要的特性是对数据集在节点间的分区进行控制,因为在分布式系统中,通信的代价是很大的,因此控制数据分布以获得最少的网络传输可以极大地提升整体性...

541
来自专栏简书专栏

Python数据分析及可视化-小测验

本文中测验需要的文件夹下载链接: https://pan.baidu.com/s/1OqFM2TNY75iOST6fBlm6jw 密码: rmbt 下载压缩包...

1722
来自专栏生信宝典

R语言学习 - 箱线图一步法

箱线图 - 一步绘制 绘图时通常会碰到两个头疼的问题: 有时需要绘制很多的图,唯一的不同就是输入文件,其它都不需要修改。如果用R脚本,需要反复替换文件名,繁琐又...

3145
来自专栏HansBug's Lab

算法模板——Dinic最小费用最大流

实现功能:输入M,N,S,T;接下来M行输入M条弧的信息(包括起点,终点,流量,单位费用);实现功能是求出以S为源点,T为汇点的网络最大流的最小费用 其实相当的...

3626
来自专栏小鹏的专栏

ubuntu下C++如何调用matlab程序

实验平台:   ubuntu  matlab R2016b   g++ 步骤: 1.    设置matlab的编译器 在命令行窗口下,输入并执行如下命令:m...

25610
来自专栏落影的专栏

OpenGLES进阶教程8-obj文件和mtl文件解析

教程 距离上一篇教程已经有两个月了,这两个月详细阅读GPUImage的源码,并写了详细解析,发现对OpenGLES的深入了解很有帮助。 上周一个简书的朋友问我...

3677

扫码关注云+社区