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

相关文章

来自专栏AI星球

如何实现大数据集查询?Bloom Filter或许是你想要的

虽然上面描述的这几种数据结构配合常见的排序、二分搜索可以快速高效的处理绝大部分判断元素是否存在集合中的需求。但是当集合里面的元素数量足够大,如果有500万条记录...

1535
来自专栏平凡文摘

你真的很熟分布式和事务吗?

1752
来自专栏芋道源码1024

从一次 Snowflake 异常说起

1. 异常概述 2018年1月26日下午,业务方信贷小组的同学反馈服务执行数据库插入操作出现异常,异常信息显示数据库主键出现重复: ? 在仔细分析了用户的重复主...

2.2K5
来自专栏数据小魔方

左手用R右手Python系列之——noSQL基础与mongodb入门

12月的第一天,祝所有小伙伴儿的12月都能够被温柔以待。 能在学校悠哉写推送的日子所剩不多了,为了珍惜剩下所剩不多的推送机会,打算12月写一些实践性强一些的内...

4337
来自专栏IT技术精选文摘

饿了么《分布式时序数据库 - LinDB》

2323
来自专栏程序你好

幽默的程序员:10 个有趣的程序员笑话

702
来自专栏平凡文摘

你真的很熟分布式和事务吗?

1113
来自专栏我杨某人的青春满是悔恨

函数式思维

自从大四看了三章《SICP》之后我就自诩为一个函数式编程爱好者,之前也在公司分享过一个 Haskell 的 Topic,效果非常糟糕,讲到后来已经没剩几个人了,...

621
来自专栏精讲JAVA

你真的很熟分布式和事务吗?

微吐槽 hello,world. 不想了,我等码农,还是看看怎么来处理分布式系统中的事务这个老大难吧! 本文略长,读者需要有一定耐心,如果你是高级码农或者架构师...

1999
来自专栏Java Edge

观察者模式

3117

扫码关注云+社区