MapReduce框架下的查询结果共享

当前的大规模数据分析通常在MapReduce框架下执行查询。由于MapReduce框架本身的冗余性以及查询之间的重叠性,复用已有查询的结果可以大幅提高查询的执行效率。复用查询的结果需要对其进行存储和匹配管理,产生高昂的系统开销,抵消复用的部分效果。本文针对目前先进的查询结果复用系统ReStore在管理查询结果和匹配中存在的效率低下的问题,提出森林结构的Job存储管理技术和与之相适应的匹配算法,提高查询的匹配效率,减少系统的开销。为了使系统能够充分复用已执行查询的结果,本文提出对多个查询进行预处理的方案,通过改变各查询进入Pig编译器进行编译的顺序,从而改变Job的执行顺序,使得加载相同数据集的Job同时执行,减少与存储库进行匹配的次数。实验表明：在构建存储结构与匹配已有结果过程中,本文提出的方法与ReStore相比,节约16.3%的时间开销,伸缩性也更好。     

MapReduce模型下基于R树索引的Skyline查询算法

提出一种MapReduce并行计算模型下基于R树索引的Skyline查询算法, 解决了海量空间数据集下执行Skyline查询效率低的问题. 通过建立R树索引实现空间数据不同粒度的范围剪枝, 有效降低了分布式Skyline查询需扫描的数据规模, 提高了在MapReduce模型下Skyline查询的执行效率. 在不同数据分布下进行对比实验的结果表明, 该方法比已有算法在执行效率上更具优势.     

云环境下海量语义数据的查询策略

为了实现对海量RDF数据的高效查询,研究RDF数据在分布式数据库HBase中的存储方法。基于MapReduce设计海量RDF数据的两阶段查询策略,将查询分为SPARQL预处理阶段与分布式查询执行阶段。SPARQL预处理阶段设计实现基于SPARQL变量关联度的查询划分算法JOVR,通过计算SPARQL查询语句中变量的关联度确定连接变量的连接顺序,根据连接变量将SPARQL子句连接操作划分到最小数量的MapReduce任务中;分布式查询执行阶段执行SPARQL预处理阶段划分的MapReduce任务,实现对海量RDF数据的并行查询。采用LUBM标准测试数据集对查询策略予以验证。研究结果表明:JOVR算法能够高效地实现对海量RDF数据的查询,并具有较强的稳定性与可扩展性。     

基于MapReduce和HBase的 海量网络数据处理

根据ERF数据的特点结合分布式框架Hadoop针对海量数据的计算优势,改进了网络数据的解析模式和数据存储模式,完成了ERF网络数据自动上传。根据XML文件解析多种类型的网络数据、HBase存储数据和HBase数据导入与数据查询的优化等一系列网络数据自动化处理工作。提出了一种新的MapReduce解析二进制数据的算法,该方案有效的解决了MapReduce读取和解析二进制数据的问题,在此基础上实现的海量网络数据处理系统,解析效率较高,数据库存储和查询数据的速度较快,系统自动化运行且稳定性强,有良好的应用前景。     

MapReduce框架下基于抽样的分布式K-Means聚类算法

提出一种MapReduce框架下基于抽样的分布式K-Means聚类算法,解决海量数据环境下并行执行K-Means算法时,时间开销较大的问题.该算法使用抽样方法,在保证数据分布不变的前提下,对数据集的规模进行约减,并在MapReduce框架下对聚类算法进行优化.实验结果表明,该算法在保持良好聚类效果的同时,能有效缩短聚类时间,对大规模数据集具有较高的执行效率和较好的可扩展性.     

基于动态获取高频率键的MapReduce性能优化算法

在云计算技术领域中,MapReduce能够帮助人们快速处理海量数据,因此在学术界以及工业界越来越受到重视。但是MapReduce在处理以文本为中心的应用时,中间结果中数据重复较多。针对该情况,已有的高频率缓冲(frequency buffering,FB)算法提出在环形内存缓冲之前添加哈希表,并将高频率键存储在哈希表中。该算法通过采样来实现,有额外开销并且统计出的高频率键并不一定准确。该文提出一种基于动态获取高频率键的MapReduce性能优化算法,通过在环形内存缓冲之前增加计数Bloom过滤器(counting Bloom filter,CBF)和哈希表,将高频率键动态地存储在哈希表中。该算法获得的高频率键更准确,同时大大减少了数据排序和磁盘I/O的开销。实际测试结果表明:该算法明显提高了作业的执行速度,比原始MapReduce提高17.04%,比FB算法提高9.31%。     

基于云计算的Apriori算法设计

对云计算技术和数据挖掘进行研究,分析Apriori算法,针对其局限性,提出优化方案,引入云计算中MapReduce模型,实现并行化。提出一种基于MapReduce的频繁项集挖掘方法,以提高算法的运行效率,降低算法执行所需的开销。     

一种高效通用WEB查询系统设计方法

针对当前WEB信息查询系统应用广泛且查询需求复杂的现状,论文给出构建可复用WEB信息查询系统的设计框架.在设计过程中,充分采用当前先进成熟的设计方法和技术,如XML、XSLT、Web Service、Enterprise Library等.此框架能实现异构数据查询、自动分析业务类型、统一的数据访问和共享查询条件界面及显示查询结果界面.在此基础上,开发人员通过简单配置和少量代码编写即可快速开发出满足客户需要的WEB信息查询系统.此框架复用度高,应用到查询系统中能提高开发效率,降低维护成本,而且构建的系统具有高扩展性和可移植性,极大地减少WEB查询系统的开发和维护工作.     

基于聚集块的多用户连续K最近邻多线程查询

当对城市道路网络中的对象进行查询时,已研究出连续的K近邻查询技术,但在一般情况下服务器会同时收到多个查询请求,为了提高查询效率,降低多查询代价,提出一种聚集块的共享查询算法并建立多用户连续查询处理框架,采用流水线处理策略,将查询分为查询预处理、查询执行及查询结果分发3个执行阶段,利用扩展树存储查询结果。实验结果表明,在目标点分布比较密集的情况下,本算法明显优于其它算法。     

并行化的Apriori算法在海量医疗文档数据挖掘中的应用及优化?

针对海量医疗文档数据中巨大潜在价值难以有效挖掘的现状,构建了基于NoSQL和MapReduce的存储与挖掘系统MSPM.通过以键值对形式存储,使复杂异构的医疗文档数据归结为统一的且适于被经典Apriori算法利用的事务数据格式,并通过挖掘MapReduce过程化,一次性全局扫描和兴趣集规约计数等优化策略,有效解决了Apriori算法在医疗大数据应用中开销大、执行速度慢和有效性差的问题.     

MapReduce框架下k-支配轮廓查询算法

随着维度和数据量的不断增长,已有的轮廓查询方法已无法为用户提供更好的查询支持.本文采用并行处理框架MapReduce 结合k-支配轮廓查询算法来解决此类查询问题.在对输入的数据集进行预排序的基础上,提出了基于MapReduce 的单轮扫描算法和双轮扫描算法,通过在不同维度、数据分布、节点个数等方面的实验测试及对比,验证了算法的有效性.     

应用动态生成树的GPU显存数据复用优化

针对手工优化GPU(Graphic Processing Unit)显存级数据复用过程复杂和编译时优化数据复用开销过大的问题,提出了一种基于动态生成树在运行时进行数据复用的优化方法,可为程序员提供一种透明且高效简单的优化方式.该方法将已经执行的GPU计算任务的数据访问抽象为生成树的叶子节点,利用动态生成树管理GPU数据访问信息,实现了运行时GPU显存级数据的复用优化,并通过运行时对生成树的搜索和维护,动态地发掘和优化GPU显存级数据复用,因此,在编程时不需要进行复杂且困难的数据复用分析,直接调用文中提出的运行时库就能有效减少程序执行过程中CPU内存和GPU显存之间的冗余数据传输次数,从而提升应用的运行性能.实验结果表明,使用文中提出的优化方法可有效消除未进行数据复用优化的CPU-GPU应用程序中的冗余数据传输,最大加速比达原始执行的3～10倍,额外开销不到优化后程序总执行时间的5％.     

基于MapReduce的关系型数据仓库并行查询

针对MapReduce框架与传统关系型数据库兼容性不好的问题,提出了一种基于分块结构的分布式关系数据库ChunkDB.并对MapReduce架构进行了扩展设计,使ChunkDB与MapReduce有效结合,将MapReduce的扩展性、易操作性、高并行性与关系数据库的索引等查询优化优势相结合.实验证明基于MapReduce的ChunkDB数据库能够为数据仓库应用提供快速高效的并行查询.     

Struts，Hibernate与XML在大型Web开发中的应用

提出了以Struts为表现层框架、Hibernate为持久层框架、XML为系统关键数据存储的设计思路。指出,将这3种技术整合应用到煤矿安全纠察综合应用系统后,可充分发挥其各自的优点,可将视图与业务逻辑剥离,最大限度地减少耦合,提高代码的可读性、重用性,提高软件的开发效率、执行效率,降低软件的维护成本。     

基于领域知识复用的需求建模

为了准确地获取和复用军事电子信息系统需求,提出了基于领域知识复用的需求建模方法.介绍了利用领域知识进行需求建模的过程,利用目标模型表达用户需求,并通过复用领域知识建立目标模型;通过目标查询匹配和复用获取目标相关需求,建立应用本体;利用顶层本体概念与MEISRDL业务框架的映射关系,根据应用本体生成需求模型.实例表明,通过复用领域知识,不仅保证了需求模型的质量,而且提高了需求建模的效率.     

分布式Top-k子图匹配技术

Top-k子图匹配是一种应用广泛的图搜索技术。相比于单机环境,分布式环境下的Top-k子图匹配问题具有更大的挑战性。该文分析了已有方法在分布式环境下存在的问题,提出了包括查询拆分、查询执行、结果连接3个步骤的算法。算法通过查询拆分,彻底避免了生成中间结果过程中的数据传输,同时通过优化查询执行和结果连接步骤,避免不必要的中间结果生成,降低单个节点的计算量,提升整体效率。在此基础上,该文对分布式环境下Top-k连接策略进行了进一步优化。在真实图数据上进行的实验测试表明:该文提出的算法能够有效解决分布式环境下Top-k子图匹配问题,具有很好的扩展性,而且使用优化连接策略的算法性能较基础算法的效率有明显的提升。     

一种基于Hadoop的大规模图最短路径查询方法

图的最短路径查询作为图论的经典问题,广泛应用于现实世界的许多应用中.然而随着图的规模日益增大,传统单机环境下的查询算法已无法满足大规模图的处理需求.为解决上述问题,提出基于Hadoop的大规模图最短路径查询方法(D-CH方法):首先利用经典的图分割算法(CNM算法)将存储于Hadoop分布式文件系统(HDFS)中的大规模图进行分割,给出了适于后续算法的标记分割结果;然后将查询区分为分割后子图内查询和子图间查询,基于MapReduce编程模型分别给出相应的并行化查询处理算法.实验结果表明,D-CH方法对大规模图的最短路径查询具有良好的执行效率.     

Hadoop平台下MapReduce模型调度算法研究

针对Hadoop默认FIFO调度算法和Fair调度算法、Capacity调度算法的不足,引入了一种基于优先权的自适应MapReduce调度算法.该算法利用作业权值为不同的Job分配不同的系统资源,同时根据各TaskTracker节点反馈回来的消息调整可执行队列的长度,以达到各节点负载平衡,提高系统的执行效率.     

异构云环境下MapReduce高效性的优化研究

为提高MapReduce在异构云计算环境下的执行效率,提出一种异构环境下基于负载类型的自适应调度算法——adaptive scheduler based on workload type in heterogeneous environment(ASBT-HE),通过反馈运行结果到Job Tracker,将后续任务根据负载类型分配到相应的Task Trackers上。但为满足用户的Qo S需求、更好的平衡系统负载,将该算进一步法优化为Better ASBT-HE(BASBT-HE)。BASBT-HE能够在考虑Qo S约束的基础上根据负载情况自动调整ASBT-HE中队列的长度。仿真实验结果表明优化后的MapReduce在异构云计算环境下具有高效性,并且考虑了用户Qo S需求,简化了系统参数配置。     

PipelineJoin:一种新的基于MapReduce的多表连接算法

MapReduce是一个并行分布式计算模型,已经被广泛应用于处理两个或多个大型表的连接操作.现有的基于MapReduce的多表连接算法,在处理链式连接时,不能处理多个大表的连接,或者需要顺序运行较多的MapReduce任务,效率较低.为此提出了一种基于MapReduce的多表连接算法——PipelineJoin,高效地实现任意多个大表的链式连接.PipelineJoin采用流水线模型和调度器来实现MapReduce任务的流水线式执行,从而有效提高多表连接的效率,同时可以较好地克服链式多表连接算法的缺陷.最后,在不同规模的数据集上进行了大量实验,实验结果表明PipelineJoin算法与原有链式多表连接算法相比,可以有效减少连接所需的时间.