云环境下海量XML文档的分布式Twig查询处理算法的研究与实现

摘要

随着互联网的迅速发展，XML已经成为互联网上信息存储和数据交换的重要标准，因此，XML文档的数据规模急剧增长，使得海量XML文档的查询处理成为当前比较热门的研究方向。XML文档查询的核心操作是小枝模式(Twig)查询，但是传统的Twig查询处理算法在海量XML文档上的查询效率低，高效地查询处理海量XML文档的研究还很少，并且存在许多问题。
　　云计算是当前处理海量数据的主流技术，云环境下海量数据管理技术研究主要包括数据分片和分布式查询处理。首先，在数据分片方面，本文提出了XML文档的任意分片算法AF(Arbitrarily Fragmentation)，AF算法能够在保证分片的任意性的前提下，通过记录分割结点信息以维持XML文档结构信息的完整性。其次，在分布式查询处理方面，本文提出了基于MapReduce的分布式Twig查询处理算法DTS(DTwigStack)，该算法利用AF算法记录的分割结点信息，分布式的处理所有的分片，并输出所有可能组合成最终的查询匹配结果的局部结果。然后，为了保证把有可能合并成最终结果的局部路径结果发送到同一个Reduce任务进行处理，本文引入了ComMapReduce框架中的Coordinator节点，用来收集DTS算法在Map阶段执行得到的键值信息，并在整合之后发送给所有的Mapper节点，重新修改键值，从而保证能够把具有相同键值的局部路径结果发送到同一个Reduce任务，并组合成最终的匹配结果。
　　本文设计了一系列实验，包括分布式查询处理算法DTS的性能与Hadoop集群slave节点数之间的关系以及与数据大小之间的关系，并且对DTS算法的加速比，可扩展性和规模增长性的性能进行了实验。实验表明分布式DTS算法在海量XML文档的查询上具有良好的性能。

目录

声明

摘要

第1章 绪论

1．1 研究背景

1．2 研究目的与意义

1．3 本文主要工作

1．4 本文组织结构

第2章 相关研究工作

2．1 XML文档

2．1．1 XML文档

2．1．2 数据模型

2．2 XML编码

2．2．1 区间编码

2．2．2 前缀编码

2．2．3 其他编码

2．3 Twig查询处理

2．3．1 Twig查询模式

2．3．2 传统的Twig查询处理算法

2．3．3 其他的Twig查询处理

2．4 云计算

2．5 本章小结

第3章 XML文档的任意分片算法

3．1 MapReduce特性分析

3．2 云环境下XML文档分片存在的问题

3．3 任意分片处理方法

3．3．1 分片情况处理

3．3．2 任意AF分片算法

3．4 本章小结

第4章 基于MapReduce的Twig查询处理

4．1 分布式DTS算法

4．1．1 全局键值的生成策略

4．1．2 分布式DTS算法

4．2 ITwigStack算法

4．2．1 TwigStack算法

4．2．2 ITwigStack算法

4．2．3 IShowSolutons算法

4．3 本章小结

第5章 实验及结果分析

5．1 实验性能评估标准

5．2 实验环境及实验设计

5．2．1 实验环境

5．2．2 实验数据集

5．2．3 实验方案

5．3 实验结果分析

5．3．1 slave节点的多少对性能的影响

5．3．2 文档大小对算法性能的影响

5．3．3 DTS算法的加速比性能

5．3．4 DTS算法的规模增长性性能

5．3．5 DTS算法的可扩展性性能

5．4 本章小结

第6章 总结与展望

6．1 总结

6．2 展望

参考文献

致谢

攻读硕士学位期间参加的项目和发表的论文