基于云计算技术的受限网络数据聚集索引的研究
基于云计算技术的受限网络数据聚集索引的研究[20191213091248]
摘 要
随着智能交通的不断快速发展，基于时空的网络数据流（以道路网上移动对象的时空信息为例）的理论和技术已经成为数据库领域的研究热点。数据流具有连续性、实时性、大小无界性、一遍扫描性等特点，但内存资源有限，如何对快速变化的连续数据流进行聚集查询已经成为数据流领域的一个重要研究方向。随着数据量的急剧增加形成海量数据流数据，传统的集中式数据存储与查询处理方法已经无法满足应用的需求。云平台所具有的高伸缩性、高扩展性、高容错性和强大的并行处理能力，为海量数据流的存储与处理能力提供了新动力。
本文的主要工作如下：
（1）、本文研究了一些比较典型的受限网络聚集索引技术，重点研究了DSD+索引技术，以及该索引技术的构建算法、更新算法以及查询算法。
（2）、在DSD+聚集索引技术基础上，设计了基于Hadoop平台的交通流数据的区域查询方法，解决了随着交通流数据增长的海量数据的存储问题和聚集查询问题，并结合MapReduce技术，对查询区域进行合理划分，提高了用户查询的效率。
（3）、通过实验进一步研究了DSD+技术在空间需求和查询质量上的优势；验证了相比基于传统的单机模型，基于Hadoop平台的交通流数据查询技术，在时间消耗上的优势；并且研究分析了Hadoop系统中，不同的Mapper数对查询效率的影响。
查看完整论文请+Q: 351916072
关键字:字受限网络、路网数据流、聚集查询、DSD+、云平台、Hadoop、MapReduce
目 录
摘 要 I
Abstract II
第一章 绪论 1
1.1研究背景 1
1.2国内外研究现状 3
1.2.1数据流管理系统 3
1.2.2分布式系统 4
1.2.3时空聚集索引方法 8
1.3本文的研究目标 8
1.4本文的结构 9
第二章 相关研究 10
2.1 DBMS和DSMS研究分析 10
2.1.1 DBMS的数据处理模型 10
2.1.2 DSMS的数据处理模型 11
2.1.3数据流模型存在的问题 12
2.2云计算技术简介 13
2.2.1 云计算的特点和优势 13
2.3 Hadoop相关技术 14
2.3.1 Hadoop分布式文件系统（HDFS） 14
2.3.2 MapReduce编程模型 16
2.4 时空聚集索引结构 19
2.4.1 Sketch索引结构 19
2.4.2 AMH+索引结构 22
2.5 道路网模型和直方图 25
2.6 本章小结 27
第三章 基于Hadoop的时空数据索引方法 28
3.1 DSD+索引结构 28
3.1.1 DSD+维护更新算法 31
3.1.2 DSD+索引结构的聚集查询 32
3.2 基于HDFS的数据操作 34
3.3基于Hadoop系统的聚集查询方法 36
3.3.1分布式数据流聚集查询模型 36
3.3.2基于Hadoop的数据查询方法 36
第四章 实验过程及分析 39
4.1 实验数据 39
4.2 实验设计与分析 39
4.2.1 实验环境 39
4.2.2 实验分析 40
第五章 总结与展望 45
5.1 总结 45
5.2 展望 45
参考文献 46
致谢 48
第一章 绪论
1.1研究背景
城市在发展，人们的生活水平在提高，街上林立的高架桥还有每日长龙般汹涌奔腾的车流提醒着人们，城市交通发展的快速应经不能用日新月异来形容了。交通运输也作为国民经济的基础产业，对经济的发展和社会的进步具有极其重要的作用，当今世界无不存在着交通拥堵问题，尤其是上下班的高峰时期，严重影响了人们的出行。面对当今世界全球化、信息化的发展趋势，传统的交通技术和手段已不适应经济社会发展的需求，在这种形势下，大范围普及智能交通系统（Intelligent Transportation System，ITS）[1]成为治理城市交通的一个重要措施。
智能交通系统是一个基于现代电子信息技术面向交通运输的服务系统。它的突出特点是以信息的收集、处理、发布、交换、分析、利用为主线，为交通参与者提供多样性的服务。如图1.1所示，城市交通信息系统由三大部分所组成：信息采集、路网环境、通信网络，进而提供服务职能、管理职能以及运行监测的功能。
图1.1 城市交通信息系统
智能交通的应用领域非常广泛。在我国，ITS出现最早、应用最多的领域主要包括以下三方面：
（1）、不停车收费系统，简称ETC系统，是以现代通信技术、电子技术、自动控制技术、计算机技术和网络技术等高新技术为主导，实现车辆不停车自动收费的智能交通系统。
（2）、电子警察，电子警察是一种利用自动化监测与测量技术捕获交通违法或交通事故，利用网络将采集的信息传回公安部门进行分析处理，并以此为证据对肇事者进行处罚，以减少事故发生、辅助交警工作的方法。
（3）、GPS，GPS即全球定位系统（Global Positioning System）。它是具有全球性、全能性（陆地、海洋、航空与航天）、全天候优势的导航定位、定时、测速系统。GPS主要由空间卫星系统、地面监控系统、用户接收系统三大子系统构成，已广泛应用于军事和民用等众多领域。
智能交通系统在时间上和空间上具有很大的相关性。如交通流数据，只有在与一定的时间和路段相联系时才具有意义。数据流的特征可概括为：实时性、无限性、瞬时性、流速不定性等。针对这些特征，传统的数据处理技术（如DBMS）已经不能够满足其需求，因此，研究合适的数据流处理技术是相当关键的。在数据流相关系统中，高质量的近似聚集应答结果可以代替精确结果，因此近似聚集查询处理便发展成为数据流中聚集处理技术的主要研究热点之一。同时云计算技术以其自动化计算及资源调度和高速信息的部署以及其优异的可扩展性，成为解决海量数据处理问题的关键技术手段，市场应用前景广阔。
随着经济的迅速发展，私家车也日益增多，即使存储的是概要信息，经过长时间之后数据量也很庞大，如果保存在单一服务器上，当数据流大于该服务器所能处理的最大数据流时，或者这个服务器发生故障时，用户的查询将得不到响应，因此，如何对快速变化的连续数据流进行聚集查询已经成为数据流领域的一个重要研究方向。云平台所具有高伸缩性、高扩展性、高容错性和强大的并行处理能力为海量数据流的存储与处理提供了新的动力。本文将采用分布式架构，研究云平台下，面向聚集查询的受限网络数据索引技术，利用MapReduce并行计算技术提高查询处理的效率。解决了分布式数据流到达的存储问题、查询问题和用户的实时性需求。并通过实验验证其正确性，为智能交通系统的进一步发展提供有力的支撑。
1.2国内外研究现状
本文主要关注的是与位置、速度等具体信息无关的聚集索引结构的查询，而建立该结构的数据源来自不同的分布式站点。因此，本小结首先分析了数据流管理系统的研究现状，接着引出分布式系统研究现状，最后介绍了时空聚集索引的研究内容及现状。
1.2.1数据流管理系统
本章介绍数据库管理系统（DataBase Management System，简称DBMS）及其数据处理模型，分析其局限性，从而引出数据流处理模型，并将其与传统的数据处理模型作比较，分析得出在数据流上进行聚集查询更重要。
典型的数据流管理原型系统[11]：
目前，国外部分起步较早的项目已经完成了具有基本功能的研究用的原型系统的开发，比较典型的原型系统有STREAM系统、Aurora系统和TelegraphCQ系统等。
（1）、STREAM是Stanford 大学研究开发的基于关系的通用数据流管理原型系统，重点研究了内存资源管理和近似查询处理，定义了一种描述性查询语言CQL（Continuous Query Language），用户可以用CQL语言进行查询注册，也可以直接输入查询计划。系统对连续、无界、随时间变化的数据流进行实时的查询处理，为各种形式的连续查询提供连续、实时的结果。
（2）、Aurora是Brandies 大学、Brown 大学和M.I.T.合作研究开发的数据流管理系统原型，主要是面向各种类型的实时监控应用领域，其核心部分是一个大型触发器网络，能够执行编译时和运行时优化。系统定义了称为Boxes 操作符而不是使用类似于SQL的查询语言，并为用户提供了一个图形化界面用操作符来定义每个触发器。
（3）California 大学Berkeley分校的TelegraphCQ系统基于Eddies概念实现了一个自适应查询处理引擎，系统主要面向传感器网络，由于面向传感器网络的DSMS 系统需要首先考虑能源有效性、时间延迟和感知精度等问题，与面向互联网应用的DSMS 系统有着显著的区别。
另外，Conell 大学的COUGAR系统，印第安大学的dQUOB 系统等都是一些正在进行研究与开发的DSMS 原型系统。国内很多大学和研究机构也正在进行DSMS 算法理论与系统实现技术的研究。
1.2.2分布式系统
与并行系统类似，分布式系统[9]的设计目的也是为了将计算复杂的大任务划分为若干个计算量稍小的任务进行处理，然后通过一系列调度算法汇总得到最终的计算结果。
Google的GFS
Google文件系统（Google File System-GFS）被设计用来满足Google迅速增长的数据处理需求。GFS与过去的分布式文件系统用有许多相同的目标，例如性能、可伸缩性、可靠性以及可用性。然而，Google在设计并实现其GFS时所考虑的目标和以往的分布式文件系统又有着一些不同的地方，具体表现在：
一、组件失效不再被认为是意外，而被看做正常的现象。这个文件系统包括几百甚至几千台普通廉价部件构成的存储机器，又被相应数量的客户机访问。组件的庞大数量和参差不齐的质量状况，使得在任何给定时间，某些组件无法工作，而某些组件无法从他们的目前的实效状态恢复是常见的情况。
二、重新设计预期和参数。传统情况下快速增长的数据集在容量达到数T，对象数达到数亿的时候，即使文件系统支持，处理数据集的方式也就是笨拙地管理数亿KB尺寸的小文件。所以，设计预期和参数，例如I/O操作和块尺寸都要重新考虑。
三、在Google大部分文件的修改，不是覆盖原有数据，而是在文件尾追加新数据。
四、应用程序和文件系统API的协同设计提高了整个系统的灵活性。例如，GFS的设计者放松了对GFS一致性模型的要求，这样不用加重应用程序的负担，就大大的规约了文件系统的设计。
为了不同的应用，Google已经部署了许多GFS集群。最大的一个，拥有超过1000个存储节点，超过300T的硬盘空间，被不同机器上的数百个客户端连续不断的频繁访问着。具体GFS架构如图1.2所示：
图1.2 GFS的架构
Apache的Hadoop[5]
Hadoop最早是作为一个开源搜索引擎项目Nutch的基础平台而开发的，后来随着项目的紧张，Hadoop被作为一个单独的开源项目进行开发。Hadoop作为一个开源的软件平台，使得编写和运行用于处理海量数据的应用程序更加容易。作为一个分布式系统平台，Hadoop具有以下一些优势：
可扩展性：Hadoop可以可靠的存储和处理petabytes级别的数据 。
经济性：Hadoop将数据分布到由廉价PC组成的集群中进行处理，这些集群可以有成千上万个节点组成。
有效性：通过数据分发，Hadoop可以在不同的节点上并行处理数据。这使得数据处理过程大大提速。
可靠性：Hadoop自动维护一份数据的多个拷贝，并自动将失败的计算任务进行重新部署。
Amazon的SimpleDB
在软件行业中，云计算（Cloud Computing）的领域在近几年的发展相当迅速。Amazon于2007年底推出了SimpleDB的Beta版，这是一个对结构化数据进行实时查询的Web服务。
SimpleDB作为一个基于Web Service的“在线数”据库，具有以下特点：
使用简单：Amazon SimpleDB规约了传统的通过关系型数据库集群才能达到的查找和查询功能的访问，同时去除了其他的一些复杂型和无用的数据库操作。SimpleDB服务通过一系列简单的API调用实现快速的数据添加、获取和编辑操作。
灵活性：借助于Amazon SimpleDB，无需为存储数据进行预先的数据格式定义，只需将新属性添加到自己的Amazon SimpleDB数据集中即可，SimpleDB系统会自动索引存储的数据。这种无需事先定义存储策略的能力给开发人员在开发应用程序时提供了极大的灵活性。
可扩展性：Amazon SimpleDB通过添加“域”的方式方便的适应数据存储或访问量的增长。在SimpleDB的Beta版本发布时，一个单独的域被限制在10GB的容量大小，一个用户最多允许创建不超过100个域。随着SimpleDB的不断发展，在今后的版本中这个限制也将逐渐得到放宽。
摘 要
随着智能交通的不断快速发展，基于时空的网络数据流（以道路网上移动对象的时空信息为例）的理论和技术已经成为数据库领域的研究热点。数据流具有连续性、实时性、大小无界性、一遍扫描性等特点，但内存资源有限，如何对快速变化的连续数据流进行聚集查询已经成为数据流领域的一个重要研究方向。随着数据量的急剧增加形成海量数据流数据，传统的集中式数据存储与查询处理方法已经无法满足应用的需求。云平台所具有的高伸缩性、高扩展性、高容错性和强大的并行处理能力，为海量数据流的存储与处理能力提供了新动力。
本文的主要工作如下：
（1）、本文研究了一些比较典型的受限网络聚集索引技术，重点研究了DSD+索引技术，以及该索引技术的构建算法、更新算法以及查询算法。
（2）、在DSD+聚集索引技术基础上，设计了基于Hadoop平台的交通流数据的区域查询方法，解决了随着交通流数据增长的海量数据的存储问题和聚集查询问题，并结合MapReduce技术，对查询区域进行合理划分，提高了用户查询的效率。
（3）、通过实验进一步研究了DSD+技术在空间需求和查询质量上的优势；验证了相比基于传统的单机模型，基于Hadoop平台的交通流数据查询技术，在时间消耗上的优势；并且研究分析了Hadoop系统中，不同的Mapper数对查询效率的影响。
查看完整论文请+Q: 351916072
关键字:字受限网络、路网数据流、聚集查询、DSD+、云平台、Hadoop、MapReduce
目 录
摘 要 I
Abstract II
第一章 绪论 1
1.1研究背景 1
1.2国内外研究现状 3
1.2.1数据流管理系统 3
1.2.2分布式系统 4
1.2.3时空聚集索引方法 8
1.3本文的研究目标 8
1.4本文的结构 9
第二章 相关研究 10
2.1 DBMS和DSMS研究分析 10
2.1.1 DBMS的数据处理模型 10
2.1.2 DSMS的数据处理模型 11
2.1.3数据流模型存在的问题 12
2.2云计算技术简介 13
2.2.1 云计算的特点和优势 13
2.3 Hadoop相关技术 14
2.3.1 Hadoop分布式文件系统（HDFS） 14
2.3.2 MapReduce编程模型 16
2.4 时空聚集索引结构 19
2.4.1 Sketch索引结构 19
2.4.2 AMH+索引结构 22
2.5 道路网模型和直方图 25
2.6 本章小结 27
第三章 基于Hadoop的时空数据索引方法 28
3.1 DSD+索引结构 28
3.1.1 DSD+维护更新算法 31
3.1.2 DSD+索引结构的聚集查询 32
3.2 基于HDFS的数据操作 34
3.3基于Hadoop系统的聚集查询方法 36
3.3.1分布式数据流聚集查询模型 36
3.3.2基于Hadoop的数据查询方法 36
第四章 实验过程及分析 39
4.1 实验数据 39
4.2 实验设计与分析 39
4.2.1 实验环境 39
4.2.2 实验分析 40
第五章 总结与展望 45
5.1 总结 45
5.2 展望 45
参考文献 46
致谢 48
第一章 绪论
1.1研究背景
城市在发展，人们的生活水平在提高，街上林立的高架桥还有每日长龙般汹涌奔腾的车流提醒着人们，城市交通发展的快速应经不能用日新月异来形容了。交通运输也作为国民经济的基础产业，对经济的发展和社会的进步具有极其重要的作用，当今世界无不存在着交通拥堵问题，尤其是上下班的高峰时期，严重影响了人们的出行。面对当今世界全球化、信息化的发展趋势，传统的交通技术和手段已不适应经济社会发展的需求，在这种形势下，大范围普及智能交通系统（Intelligent Transportation System，ITS）[1]成为治理城市交通的一个重要措施。
智能交通系统是一个基于现代电子信息技术面向交通运输的服务系统。它的突出特点是以信息的收集、处理、发布、交换、分析、利用为主线，为交通参与者提供多样性的服务。如图1.1所示，城市交通信息系统由三大部分所组成：信息采集、路网环境、通信网络，进而提供服务职能、管理职能以及运行监测的功能。
图1.1 城市交通信息系统
智能交通的应用领域非常广泛。在我国，ITS出现最早、应用最多的领域主要包括以下三方面：
（1）、不停车收费系统，简称ETC系统，是以现代通信技术、电子技术、自动控制技术、计算机技术和网络技术等高新技术为主导，实现车辆不停车自动收费的智能交通系统。
（2）、电子警察，电子警察是一种利用自动化监测与测量技术捕获交通违法或交通事故，利用网络将采集的信息传回公安部门进行分析处理，并以此为证据对肇事者进行处罚，以减少事故发生、辅助交警工作的方法。
（3）、GPS，GPS即全球定位系统（Global Positioning System）。它是具有全球性、全能性（陆地、海洋、航空与航天）、全天候优势的导航定位、定时、测速系统。GPS主要由空间卫星系统、地面监控系统、用户接收系统三大子系统构成，已广泛应用于军事和民用等众多领域。
智能交通系统在时间上和空间上具有很大的相关性。如交通流数据，只有在与一定的时间和路段相联系时才具有意义。数据流的特征可概括为：实时性、无限性、瞬时性、流速不定性等。针对这些特征，传统的数据处理技术（如DBMS）已经不能够满足其需求，因此，研究合适的数据流处理技术是相当关键的。在数据流相关系统中，高质量的近似聚集应答结果可以代替精确结果，因此近似聚集查询处理便发展成为数据流中聚集处理技术的主要研究热点之一。同时云计算技术以其自动化计算及资源调度和高速信息的部署以及其优异的可扩展性，成为解决海量数据处理问题的关键技术手段，市场应用前景广阔。
随着经济的迅速发展，私家车也日益增多，即使存储的是概要信息，经过长时间之后数据量也很庞大，如果保存在单一服务器上，当数据流大于该服务器所能处理的最大数据流时，或者这个服务器发生故障时，用户的查询将得不到响应，因此，如何对快速变化的连续数据流进行聚集查询已经成为数据流领域的一个重要研究方向。云平台所具有高伸缩性、高扩展性、高容错性和强大的并行处理能力为海量数据流的存储与处理提供了新的动力。本文将采用分布式架构，研究云平台下，面向聚集查询的受限网络数据索引技术，利用MapReduce并行计算技术提高查询处理的效率。解决了分布式数据流到达的存储问题、查询问题和用户的实时性需求。并通过实验验证其正确性，为智能交通系统的进一步发展提供有力的支撑。
1.2国内外研究现状
本文主要关注的是与位置、速度等具体信息无关的聚集索引结构的查询，而建立该结构的数据源来自不同的分布式站点。因此，本小结首先分析了数据流管理系统的研究现状，接着引出分布式系统研究现状，最后介绍了时空聚集索引的研究内容及现状。
1.2.1数据流管理系统
本章介绍数据库管理系统（DataBase Management System，简称DBMS）及其数据处理模型，分析其局限性，从而引出数据流处理模型，并将其与传统的数据处理模型作比较，分析得出在数据流上进行聚集查询更重要。
典型的数据流管理原型系统[11]：
目前，国外部分起步较早的项目已经完成了具有基本功能的研究用的原型系统的开发，比较典型的原型系统有STREAM系统、Aurora系统和TelegraphCQ系统等。
（1）、STREAM是Stanford 大学研究开发的基于关系的通用数据流管理原型系统，重点研究了内存资源管理和近似查询处理，定义了一种描述性查询语言CQL（Continuous Query Language），用户可以用CQL语言进行查询注册，也可以直接输入查询计划。系统对连续、无界、随时间变化的数据流进行实时的查询处理，为各种形式的连续查询提供连续、实时的结果。
（2）、Aurora是Brandies 大学、Brown 大学和M.I.T.合作研究开发的数据流管理系统原型，主要是面向各种类型的实时监控应用领域，其核心部分是一个大型触发器网络，能够执行编译时和运行时优化。系统定义了称为Boxes 操作符而不是使用类似于SQL的查询语言，并为用户提供了一个图形化界面用操作符来定义每个触发器。
（3）California 大学Berkeley分校的TelegraphCQ系统基于Eddies概念实现了一个自适应查询处理引擎，系统主要面向传感器网络，由于面向传感器网络的DSMS 系统需要首先考虑能源有效性、时间延迟和感知精度等问题，与面向互联网应用的DSMS 系统有着显著的区别。
另外，Conell 大学的COUGAR系统，印第安大学的dQUOB 系统等都是一些正在进行研究与开发的DSMS 原型系统。国内很多大学和研究机构也正在进行DSMS 算法理论与系统实现技术的研究。
1.2.2分布式系统
与并行系统类似，分布式系统[9]的设计目的也是为了将计算复杂的大任务划分为若干个计算量稍小的任务进行处理，然后通过一系列调度算法汇总得到最终的计算结果。
Google的GFS
Google文件系统（Google File System-GFS）被设计用来满足Google迅速增长的数据处理需求。GFS与过去的分布式文件系统用有许多相同的目标，例如性能、可伸缩性、可靠性以及可用性。然而，Google在设计并实现其GFS时所考虑的目标和以往的分布式文件系统又有着一些不同的地方，具体表现在：
一、组件失效不再被认为是意外，而被看做正常的现象。这个文件系统包括几百甚至几千台普通廉价部件构成的存储机器，又被相应数量的客户机访问。组件的庞大数量和参差不齐的质量状况，使得在任何给定时间，某些组件无法工作，而某些组件无法从他们的目前的实效状态恢复是常见的情况。
二、重新设计预期和参数。传统情况下快速增长的数据集在容量达到数T，对象数达到数亿的时候，即使文件系统支持，处理数据集的方式也就是笨拙地管理数亿KB尺寸的小文件。所以，设计预期和参数，例如I/O操作和块尺寸都要重新考虑。
三、在Google大部分文件的修改，不是覆盖原有数据，而是在文件尾追加新数据。
四、应用程序和文件系统API的协同设计提高了整个系统的灵活性。例如，GFS的设计者放松了对GFS一致性模型的要求，这样不用加重应用程序的负担，就大大的规约了文件系统的设计。
为了不同的应用，Google已经部署了许多GFS集群。最大的一个，拥有超过1000个存储节点，超过300T的硬盘空间，被不同机器上的数百个客户端连续不断的频繁访问着。具体GFS架构如图1.2所示：
图1.2 GFS的架构
Apache的Hadoop[5]
Hadoop最早是作为一个开源搜索引擎项目Nutch的基础平台而开发的，后来随着项目的紧张，Hadoop被作为一个单独的开源项目进行开发。Hadoop作为一个开源的软件平台，使得编写和运行用于处理海量数据的应用程序更加容易。作为一个分布式系统平台，Hadoop具有以下一些优势：
可扩展性：Hadoop可以可靠的存储和处理petabytes级别的数据 。
经济性：Hadoop将数据分布到由廉价PC组成的集群中进行处理，这些集群可以有成千上万个节点组成。
有效性：通过数据分发，Hadoop可以在不同的节点上并行处理数据。这使得数据处理过程大大提速。
可靠性：Hadoop自动维护一份数据的多个拷贝，并自动将失败的计算任务进行重新部署。
Amazon的SimpleDB
在软件行业中，云计算（Cloud Computing）的领域在近几年的发展相当迅速。Amazon于2007年底推出了SimpleDB的Beta版，这是一个对结构化数据进行实时查询的Web服务。
SimpleDB作为一个基于Web Service的“在线数”据库，具有以下特点：
使用简单：Amazon SimpleDB规约了传统的通过关系型数据库集群才能达到的查找和查询功能的访问，同时去除了其他的一些复杂型和无用的数据库操作。SimpleDB服务通过一系列简单的API调用实现快速的数据添加、获取和编辑操作。
灵活性：借助于Amazon SimpleDB，无需为存储数据进行预先的数据格式定义，只需将新属性添加到自己的Amazon SimpleDB数据集中即可，SimpleDB系统会自动索引存储的数据。这种无需事先定义存储策略的能力给开发人员在开发应用程序时提供了极大的灵活性。
可扩展性：Amazon SimpleDB通过添加“域”的方式方便的适应数据存储或访问量的增长。在SimpleDB的Beta版本发布时，一个单独的域被限制在10GB的容量大小，一个用户最多允许创建不超过100个域。随着SimpleDB的不断发展，在今后的版本中这个限制也将逐渐得到放宽。
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/dzxx/txgc/2274.html
