论文部分内容阅读
XML已成为Web数据交换和信息表示的事实标准。随着XML数据量的急剧增长,如何对这些正在快速增长的海量XML数据有效地组织和存储,并提供高效快速的数据检索,是当今数据挖掘领域的一个研究重点。目前,XML数据的存储和检索一般还使用原生的XML数据库或者关系数据库,但这类系统无法满足海量XML数据的性能要求,而基于分布式的XML数据存储和检索技术也尚未成熟。MapReduce的出现在一定程度上缓解了上述问题。MapReduce是一种处理海量数据的有效解决方案,但是基于该框架处理海量XML数据查询问题的研究成果却很少,而且现有的分布式Twig查询算法在Map阶段需要做结构连接操作,大多会产生大量无用的中间结果,此外,这种算法往往还需要额外的查询分解操作。针对以上问题,本文提出了两种基于结点分发的查询方案:NDTH算法和DTH算法,实现海量XML数据的Twig查询处理。本文提出的两种查询方案基于结点分发的思想,即在Map阶段不做结构连接操作,而是将处于不同分片上但却可能构成查询解的结点分发到一台Reduce计算节点上,这样在Reduce阶段就可以根据查询模式的特点,选择适合该查询且性能最优的整体匹配算法,如选用对祖先后代关系性能最优或父子关系最优的整体匹配算法等。本文首先基于ComMapReduce提出了 NDTH算法,该算法利用ComMapReduce的协调者节点收集全局的键值,通过全局键值能够舍弃那些不能构成最终查询解的结点,进而提高查询效率,同时保证最终查询结果不丢失。其次,本文通过对XML数据结构和MapReduce工作原理的研究,分析了现有基于MapReduce的XML查询处理方法中,文档分片技术的局限性,提出了松弛分割算法(Relax-Fragment)。该算法能够实现对XML文档的任意分割而不需要依赖查询信息。在松弛分片策略RFS的基础上,我们设计了基于松弛分片的DTH算法,该算法利用记录了分片祖先信息的松弛分片索引,能够加快查询速度,保证并行查询结果的正确性和完整性。最后,本文采用真实数据集进行实验,对本文所提的两种分布式Twig查询处理算法的实验结果进行了详细分析。本文实验结果表明,分布式NDTH算法和DTH算法能够减少海量XML数据查询处理时间,具有较高的查询效率和良好性能。