大规模实时数据流连接关键技术的研究

发布时间：2017-07-03 02:13

  本文关键词：大规模实时数据流连接关键技术的研究

  更多相关文章： 实时数据流 连接 Compressed直方图 一致性hash (key valueList) 共享时间片

【摘要】：互联网、传感器以及物联网等技术的发展,使数据产生的速度越来越快。无处不在的数据中隐藏着各种有价值的信息,这些信息给人们的日常生活提供了便利。 在很多应用中,信息以数据流的形式提供给用户,这些信息带有很强的时效性,要求用户以"on-the-fly"的形式进行处理。另外,由于设备以及应用特点的限制,单条数据流往往只能提供部分数据,用户需要将多条数据流结合起来才能获取完整信息。连接(Join)作为获取综合信息的有效手段之一,在数据流处理中占有重要地位。 大数据时代的到来使单节点的计算模式已经不能满足数据流连接的需求,由多个‘'shared-nothing"廉价节点构成的集群成为解决该问题的有效手段之一。本文在深入研究和总结相关工作的基础上,围绕分布式环境下多路数据流的连接问题展开研究,内容主要集中在以下几个方面： 首先,在数据流模型下提出了基于增量计算的Compressed直方图构建和维护算法。在允许的误差范围内,Compressed直方图可以反映当前滑动窗口中数据的大致分布情况,为接下来多路数据流的连接优化问题提供支持,该部分为后面研究的基础。 其次,针对二路数据流的特点提出了基于流水线的二路数据流连接算法。该算法将计算节点以线性形式组织,将两条数据流以相向的方式注入流水线,可以处理二路数据流等值及不等值连接,在不需要数据备份的条件下能够保证结果的完整性。另外,在流水线模型下提出了基于上游备份的容错机制、类似按压橡皮泥的负载均衡机制以及可扩展性机制等。 再次,针对多路数据流等值连接的特点提出了基于一致性hash的多路数据流等值连接分配算法,该算法在保证相关联元组能够分配到相同节点的前提下,可以维持各个计算节点间的负载均衡。另外,根据直方图提供的信息,在数据流连接过程中采用基于贪心的算法实时维持连接树,保证数据流以相对较优的顺序执行,减少网络传输及连接过程的执行时间。 最后,对通用性更强的多路数据流非等值连接进行了研究,提出了基于范围hash和共享时间片的分配策略。这两个策略在兼顾结果完整性和负载均衡的同时,也尽量减少备份数据的传递量,降低网络负载。另外,针对很多应用滑动窗口中连接属性属于多重集的情况,提出了基于(key,valueList)的"Group Join"连接算法,降低网络传输量,在某些情况下减少执行时间。 本文从分布式多路数据流连接出发,提出了适合二路数据流连接的流水线算法、适合等值连接的一致性hash算法以及适合非等值连接的范围hash和共享时间片算法,并在这些算法的基础上提出了一系列的负载均衡、容错、扩容以及连接优化算法,为后续研究研究工作提供了参考。
【关键词】：实时数据流 连接 Compressed直方图 一致性hash (key valueList) 共享时间片
【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP311.13
【目录】：

• 摘要5-7
• ABSTRACT7-9
• 目录9-12
• 插图索引12-14
• 算法索引14-15
• 第一章 绪论15-25
• 1.1 论文研究背景15-18
• 1.1.1 大数据产生背景15-16
• 1.1.2 数据流概念及特征16-17
• 1.1.3 主流数据流计算环境17-18
• 1.2 论文研究问题的提出18-22
• 1.2.1 数据流直方图的高效构建方法20
• 1.2.2 分布式环境下二路数据流连接20-21
• 1.2.3 多路数据流等值连接21
• 1.2.4 多路数据流任意连接21-22
• 1.3 论文的主要研究工作22-24
• 1.3.1 论文的研究内容22
• 1.3.2 论文的组织结构22-24
• 1.4 本章小结24-25
• 第二章 数据流连接相关技术综述25-39
• 2.1 引言25-26
• 2.2 数据流相关技术26-30
• 2.2.1 定义及分类26-27
• 2.2.2 滑动窗口27
• 2.2.3 时间戳27-28
• 2.2.4 多路数据流连接语义28-30
• 2.3 数据流连接算法30-37
• 2.3.1 单节点上多路数据流连接算法30-32
• 2.3.2 分布式环境下多路数据流连接算法32-37
• 2.4 本章小结37-39
• 第三章 数据流Compressed直方图构建算法39-51
• 3.1 引言39-40
• 3.2 背景及相关工作40-42
• 3.2.1 直方图定义及分类40-41
• 3.2.2 相关工作41-42
• 3.3 基于增量计算的Compressed直方图构建算法42-45
• 3.3.1 Compressed直方图构建算法42
• 3.3.2 基于增量计算的直方图维护策略42-45
• 3.4 实验及分析45-49
• 3.4.1 重构与维护时间对比46-47
• 3.4.2 误差因素47-49
• 3.5 本章小结49-51
• 第四章 二路数据流连接算法设计51-65
• 4.1 引言51-52
• 4.2 背景及相关工作介绍52-53
• 4.3 基于流水线的二路数据流连接算法53-60
• 4.3.1 流水线连接基本原理53-54
• 4.3.2 基于流水线连接算法54-56
• 4.3.3 容错机制56-59
• 4.3.4 可扩展性59-60
• 4.4 实验及结果分析60-64
• 4.4.1 流水线模型处理能力61-62
• 4.4.2 负载均衡62-63
• 4.4.3 容错能力63-64
• 4.5 本章小结64-65
• 第五章 多路数据流等值连接算法设计65-85
• 5.1 引言65-66
• 5.2 背景及相关工作介绍66-68
• 5.2.1 多路数据流连接分配问题66-67
• 5.2.2 连接效率问题67-68
• 5.3 基于一致性Hash的多路数据流分配算法68-73
• 5.3.1 负载均衡68-71
• 5.3.2 灾难恢复71-73
• 5.4 基于贪心的多路数据流连接73-77
• 5.4.1 基于贪心的连接树构建算法74-76
• 5.4.2 简单贪心连接树构建算法76-77
• 5.5 实验及分析77-84
• 5.5.1 负载均衡77-80
• 5.5.2 容错80-81
• 5.5.3 多路数据流连接顺序优化81-83
• 5.5.4 运算时间83-84
• 5.6 本章小结84-85
• 第六章 多路数据流任意连接算法设计85-105
• 6.1 引言85-86
• 6.2 背景及相关工作介绍86-88
• 6.2.1 多路数据流任意连接分配问题86-87
• 6.2.2 多路数据流连接问题87-88
• 6.3 多路数据流任意连接分配算法88-92
• 6.3.1 范围hash分配算法88-89
• 6.3.2 基于时间片分配算法89-92
• 6.4 基于(key,ualueList)的多路数据流连接92-96
• 6.4.1 网络传输93-94
• 6.4.2 连接操作94-96
• 6.5 实验及结果分析96-103
• 6.5.1 负载均衡97-99
• 6.5.2 (key,value)(?)(key,valueList)99-103
• 6.6 本章小结103-105
• 第七章 总结与展望105-109
• 7.1 本文工作总结105-106
• 7.2 贡献及创新点106
• 7.3 展望106-109
• 参考文献109-115
• 致谢115-117
• 在读期间发表的学术论文与取得的研究成果117

【共引文献】

中国期刊全文数据库 前10条

1 李丹;郭放;;节能变压器制造系统中的数据流管理系统研究[J];变压器;2009年02期

2 谷峪;李晓静;许嘉;于戈;;支持复杂语义的数据流滑动窗口连接建模和查询优化[J];东北大学学报(自然科学版);2008年11期

3 赵文;刘学洋;刘殿兴;王立福;;一种基于Trie树和扩展B树的RFID标签编码过滤方法研究[J];电子学报;2011年S1期

4 蒋涛;高云君;张彬;周傲英;乐光学;;不确定数据查询处理[J];电子学报;2013年05期

5 王鹏;黄焱;刘峰;安俊秀;;大数据技术中计算与数据的协作机制[J];成都信息工程学院学报;2014年01期

6 刘崇富;张子锋;孔浩;;基于J2EE架构的高校档案管理日志模块的设计与实现[J];电脑开发与应用;2014年01期

7 孙刚;周华平;孙克雷;;基于改进的随机决策树的煤矿安全评价方法[J];阜阳师范学院学报(自然科学版);2014年02期

8 田文飚;康健;张洋;芮国胜;张海波;;基于卡尔曼滤波的压缩感知弱匹配去噪重构[J];电子学报;2014年06期

9 梁源;王兴华;向新;王锋;孙晔;;一种基于贪婪算法的CORDIC改进算法[J];电讯技术;2014年03期

10 刘文才;黄薇;;浅析算法优化[J];电子制作;2014年09期

中国博士学位论文全文数据库 前10条

1 潘鹏;Deep Web查询中的不确定性问题研究[D];山东大学;2010年

2 朱辉生;基于情节规则匹配的数据流预测研究[D];复旦大学;2011年

3 侯东风;流式数据多维建模与查询关键技术研究[D];国防科学技术大学;2010年

4 甘亮;面向网络安全监控的流数据处理技术研究[D];国防科学技术大学;2011年

5 陈涛;大规模网络存储环境中的数据布局与查询优化技术研究[D];国防科学技术大学;2011年

6 邓华锋;分布式数据流处理的算子调度与负载平衡研究[D];华中科技大学;2007年

7 李俊奎;时间序列相似性问题研究[D];华中科技大学;2008年

8 苏亮;数据流分析关键技术研究[D];国防科学技术大学;2008年

9 孟和;无线内容下载平台中事件流处理应用研究[D];天津大学;2009年

10 吴枫;数据流挖掘若干关键技术研究[D];国防科学技术大学;2009年

  本文关键词：大规模实时数据流连接关键技术的研究

  更多相关文章： 实时数据流 连接 Compressed直方图 一致性hash (key valueList) 共享时间片

，

本文编号：512060