欢迎来到知嘟嘟! 联系电话:13095918853 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13095918853
知嘟嘟经纪人
收藏
专利号: 2017108057815
申请人: 广西大学
专利类型:发明专利
专利状态:已下证
专利领域: 电通信技术
更新日期:2023-12-11
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.基于EMD距离的数据流分布式相似性连接方法,其特征在于,基于开源的数据流分布式并行计算框架Apache Storm构建Storm Topology处理结构;Storm Topology处理结构由Spout和Bolt两类组件构成;数据流R和数据流S通过Spout节点将原始数据转换成直方图元组的形式并喷射给下游的Partition-bolt节点,Partition-bolt节点下游的Join-bolt节点上有多个并行执行的Join-bolt Task;Partition-bolt节点一方面基于Apache Storm框架的全局分组策略将每个来自数据流S的直方图元组广播至Join-bolt节点的每个Join-bolt Task上,然后每个Join-bolt Task为其所收到的数据流S的数据分片构建B+树森林索引;另一方面Partition-bolt节点采用基于数据局部性的数据流划分策略将来自数据流R的相似的直方图元组发送给同一个Join-bolt Task;每个Join-bolt Task在获得当前滑动窗口内数据流R和数据流S的完整数据分片之后,采用相似性连接策略对数据流R和数据流S的数据分片执行基于EMD距离的相似性连接;各Join-bolt Task在执行连接计算的过程中记录自身在当前反馈周期的连接负载并在当前反馈周期结束时以负载反馈元组的形式发送给上游的Partition-bolt节点,Partition-bolt节点收集到上一反馈周期所有Join-bolt Task提交的负载反馈元组之后,基于代价模型采用基于反馈的负载均衡策略调整当前反馈周期对数据流R的划分,实现当前反馈周期内各Join-bolt Task间的负载均衡。

2.如权利要求1所述的基于EMD距离的数据流分布式相似性连接方法,其特征在于,所述基于数据局部性的数据流划分策略为:

Partition-bolt节点首先将直方图的一维实数映射空间Ω(Z)划分为k个子空间,并规定映射至第i个子空间上的直方图元组由第i个Join-bolt Task负责处理;每当Partition-bolt节点接收到数据流R的元组,Partition-bolt将按以下公式计算该元组的键值key(P,Φ):其中,给定直方图元组P={p1,…,pn},该元组在EMD距离对偶线性规划问题的可行解Z={Φ,Π}, Π={π1,…,πn};

若该键值key(P,Φ)落在Ω(Z)的第i个子空间,则将该元组划分给第i个Join-bolt Task。

3.如权利要求1所述的基于EMD距离的数据流分布式相似性连接方法,其特征在于,所述相似性连接策略为:

每个Join-Bolt Task在获得当前滑动窗口内数据流R和数据流S的完整数据分片之后,首先在数据流S的数据流分片上构建B+树森林索引,以数据流R数据分片中的每个元组r为查询对象,访问所述B+森林索引过滤所有与所述查询对象不相似的S数据流分片上的直方图元组,得到S数据流分片上的初步约减查询候选集,再先后按新可行解过滤机制、EMD距离的下界函数LBIM过滤机制、EMD距离的上界函数UBp过滤机制和三角不等式过滤机制逐步约减S数据流分片上的所述初步约减查询候选集得到最终约减查询候选集S’;最后计算所述查询对象和最终约减查询候选集S’中每个直方图元组之间的EMD距离,若所得EMD距离值不大于相似性阈值θ,则得到所述元组r与数据流S的数据流分片之间的相似性连接结果;同时在执行连接计算的过程中记录自身在当前反馈周期的连接负载并在当前反馈周期结束时以负载反馈元组的形式发送给上游的Partition-bolt节点。

4.如权利要求1所述的基于EMD距离的数据流分布式相似性连接方法,其特征在于,所述代价模型为:

每个Join-bolt Task负责完成R数据流分片和S数据流分片之间基于EMD距离相似性连接,在一个执行周期内一个Join-bolt Task的连接代价O的模型为:

O=|R'|Ofilter+Nemd Oemd.

其中,R'表示Join-bolt Task所获得的R数据流分片,|R'|表示R'的元组基数,Ofilter表示每个R数据流元组和S数据流分片进行相似性连接时的平均过滤代价,Oemd表示EMD距离的平均计算代价,Nemd表示Join-bolt节点上实际发生的EMD距离的计算次数。

5.如权利要求4所述的基于EMD距离的数据流分布式相似性连接方法,其特征在于,所述基于反馈的负载均衡策略为:

将数据流的时间域划分为连续等长不相交的反馈周期,每个Join-bolt Task在执行相似性连接时按所述代价模型统计每个反馈周期内所发生的EMD计算次数作为其在该反馈周期的计算负载代价,并在反馈周期末将该统计信息以负载反馈元组的形式发送给上游的Partition-bolt节点;根据数据流的时间关联性,每个Join-bolt Task在时间域上相邻的两个反馈周期上统计得到的计算负载代价具有相似性,Partition-bolt节点在汇总所有Join-bolt Task在上一反馈周期统计的负载反馈元组之后,将基于这些负载反馈元组提供的信息得到直方图至各个Join-bolt  Task的新划分规则集,在下一反馈周期中,Partition-bolt节点将采用所得到的新划分规则集中的数据划分规则决定各个Join-bolt Task上的数据流划分策略。