大数据算法-第三讲-亚线性算法例析.pdf

哈南演工素大学海量数据计算研究中心

MassiveDataComputingLab@HIT

大数据算法

第三讲亚线性算法例析

哈尔滨工业大学

王宏志

wangzh@hit.edu.cn

本讲内容

3.1数据流中频繁元素

3.2最小生成树

3.3序列有序的判定

大数据的数据流模型

■数据只能顺序扫描1次或几次

■能够使用的内存是有限的

■希望通过维护一个内存结果(

概要)来给出相关性质的一个

有效估计

■数据流模型适用于大数据

■顺序扫描数据仅一次

·内存亚线性

数据流模型

■来自某个域中的元素序列

xj,x?,x?,X4,……

■有限的内存：

内存数据的规模

■快速处理每个元素

从数据流中计算什么?

容易计算的函数：min,max,sum,…

使用单个寄存器s,直接更新：

max:初始化s-0

sum:初始化s-0

对于元素x,s←s+x

“概要”是单个值

是可合并的111EILI1

频繁元素

■元素出现多次，希望找到出现最频繁的元

素

■n:不同元素的数量

■m:数据流中元素个数

频繁元素

应用：

■网络：找到“elephantflow”

■有哪些信誉好的足球投注网站：找到频繁查询

Zipf原则：典型的频率分布是高度偏斜的，只有少数

频繁元素.

最多10??元素古元素总个数的90%.

我们发现出现次数最多的元素

频繁元素：精确解

精确解：

■对每一个单独元素设置一个计数器

■当处理一个元素时，增加相应计数器

1464

3212

问题：需要维护n个计数器

但只能有kn个计数器

频繁元素计算算法

MisraGries(MG)算法

处理元素x

■If已经为x分配计数器，增加之

x分配计数器，并设为1.

■Else,所有计数器减1.删除值为0的计数器.

321214又X12n=6

k=3

m=11

频繁元素算法

处理元素x

■If已经为x分配计数器，增加之

x分配计数器，并设为1.

■Else,所有计数器减1.删除值为0的计数器.

x出现几次?

■lf我们有一个x的计数器，返回其值

■Else,返回0.

该估计显然过低

如何精确估计?

分析

一个计数器x减少了几次?

?我们有几个减少计数器的步骤?

■整个结构的权重(计数器的和)记作m

■整个数据流的权重(全部元素的数量)是m

■每一个计数器降低的步骤减少k个计数，但是并未计入

输入元素的此次出现，即k+1次未计入的元素出现.

→最多有”个减少步骤

→估计值和真实值相差最多m

分析

估计值与真实值相差最多mcr

→当数据流中元素的总数》时，得到k的一个好的

估计

■错误的界限和k成反比

■利用概要计