MapReduce框架下基于森林存储结构的查询结果共享

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

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

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

基于Web Service的数据查询平台技术

MIS系统中数据库的访问技术已经从传统的基于API的直接访问技术演化到基于面向对象的对象-关系映射（ORM）阶段.尽管ORM技术解决了应用程序和数据库系统之间＂抗阻不匹配＂不匹配的问题,但是ORM缺乏弹性和对复杂查询能力的不足.本文提出了一种基于.net的数据查询平台技术,使用Web Service技术将数据查询和业务处理进行分离,大大提高了查询的执行效率且增强了系统的鲁棒性.     

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

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

一种基于搜索树的轻量级RFID标签防碰撞方案

针对现有的RFID(radio frequency identification)搜索树防冲突方案由于查询命令过长，会产生大量的冗余数据，增加通信开销的问题，提出一种基于搜索树的轻量级防冲突方案。该方案设计了一种新颖的查询-响应模式(即单查询双响应)，该方法能够使冲突标签分别根据2个后续时隙中的最大有效冲突位对下一个查询作出响应，将查询总数减少一半；该方案用计数器代替了标签中的前缀匹配电路，可消除前缀作为查询命令的参考参数。此外，该方案提出了一种预测识别方法以减少所需时隙总数。最后，该方案还提出了一种避免识别标签与未识别标签冲突的锁定技术，提高了标签的识别效率。实验结果表明，采用双应答模式和计数器触发的单次查询方式，通信开销总体上降低了42%；采用预测识别方式，吞吐量随着标签数量的增加而提高。     

基于Hive的性能优化研究

主要从Map Reduce作业调度和Hive性能调优两个方面对Hive的性能优化进行研究.对于Map Reduce主要从编程模型切入,分析其执行过程,并从map端、reduce端进行参数调优.接着从Hive框架角度入手,分别从分区表和外部表以及常用数据文件的压缩、行式存储与列式存储等方面进行深入研究.实验结果表明,snappy压缩、orcfile/parquet存储格式对于列式查询,提高查询效率,对于大数据分析平台有较好的兼容性.     

基于OLAP查询的数据集市系统的研究

研究了通过对数据仓库视图进行水平分割来建立数据集市系统，提高OLAP查询效率的方法和技术。提出了根据OLAP查询中的选择谓词构造其最小项谓词，选择数据仓库立方体视图进行水平分割，利用视图分割后的裂片建立的数据集市来回答查询，达到减少访问的视图元组数和加快查询响应时间，从而提高OLAP查询效率，削减维护费用。     

MapReduce based computation of the diffusion method in recommender systems

The performance of existing diffusion-based algorithms in recommender systems is still limited by the processing ability of a single computer .In order to conduct the diffusion computation on large data sets, a parallel implementation of the classic diffusion method on the MapReduce framework is proposed.At first, the diffusion computation is transformed from a summation format to a cascade matrix multiplication format , and then , a parallel matrix multiplication algorithm based on dynamic vector is proposed to reduce the CPU and I/O cost on the MapReduce framework , which can also be applied to other parallel matrix multiplication scenarios .Then, block partitioning is used to further improve the performance , while the order of matrix multiplication is also taken into consideration . Experiments on different kinds of data sets have verified the efficiency of the proposed method .     

动态图上的最短路径距离并行算法

设计动态图上最短路径距离查询的并行计算框架。通过构建增量图的方法, 实现一个批次内的多个查询在不同数据图版本的多线程并发执行。对于每个查询, 使用双向宽度优先搜索算法来减少搜索空间, 并提出搜索过程中扩展方向的决策函数。利用BSR对数据图邻接表进行编码, 结合 SIMD指令和图顶点重标号算法, 进一步提升数据级并行度。在真实图数据集下的大量实验验证了所提方法的高效性。     

数据仓库中一种基于维层次编码的位图索引方法

为了减少OLAP中的多表连接,压缩维属性连接关键字,对查询数据进行有效地分组聚集操作,来提高OLAP查询速度.利用维属性具有层次特性对维成员进行编码,生成其维层次编码,来代替维表中原关键字,实现了维表关键字的压缩.通过编码长度较小的维层次编码及其层次前缀路径,对维层次编码进行前缀匹配操作,快速检索出与查询关键字相匹配的维层次编码,求得维层次属性的查询范围,从而大大减少和简化了事实表与维表之间的多表连接,减少了I/O开销,提高了OLAP查询效率.     

An Efficient Algorithm for Query Transformation in Semantic Query Optimization

Semantic query optimization (SQO)is comparatively a recent approach for the transformation of given query into equivalent alternative query using matching rules in order to select an optimal query based on the costs of executing alternative queries,The key aspect of the algorthm proposed here is that previous proposed SQO techniques can be considered equally in the uniform cost model,with which optimization opportunities will not be missed.At the same time,the authors used the implication closure to guarantee that any matched rule will not be lost .The authors implemented their algorithm for the optimization of decomposed sub-query in local database in MultiDatabase Integrator(MDBI),which is a multidatabase project.The experimental results verify that this algorithm is effective in the process of SQO.     

一种面向图集合的相似性搜索技术

目前图相似性的研究工作主要集中在子图的匹配,而没有充分关注图集合之间的匹配.针对这一问题,提出了一种基于过滤-求精框架的GSSS算法;提出了一种图集合距离定义,设计了Number,Size,Complete edge和Lower bound过滤器减小搜索空间,优化了图集合距离的计算;设计并优化了一种增量式的多层倒排索引,提高了查询效率,适应数据集的动态变化.真实数据集上的大量实验验证了GSSS算法的有效性和高效性.     

采用BWT的多核并行的子串匹配算法

针对P-BWT精确匹配算法存在只支持短串查询并且只能工作在单处理器上的问题,提出了一个多核并行的支持任意查询长度的精确查询算法.改进了P-BWT索引上的查询过程,当一个查询串跨越了多个数据分片时,首先在其匹配的最后一个分片上查询,然后依次在前面分片上进行验证.进一步提出了一个多核并行查询算法来减少搜索和验证过程的迭代次数.实验结果表明,所述算法可以高效并行地完成子串匹配任务.