原创力文档- 1、本文档共34页，可阅读全部内容。
- 2、原创力文档（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
哈南演工素大学海量数据计算研究中心
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成反比
■利用概要计
文档评论（0）