基于Hadoop的XML关键字查询算法研究

摘要

可扩展标记语言(eXtensible Markup Language, XML)，是基于标准广义标记语言，用于定义语义标记的一套规则。它已经在数据挖掘、数据库系统等诸多应用领域发挥了重要的作用。XML正在成为数据管理与存储的重要技术。为了能从海量XML数据中提取用户所需要的信息，许多XML数据查询方法应运而生，使得XML数据查询成为相关领域的一个研究热点。
　　云计算是一种可以实现程序并行化的编程模型，简单来说就是可以将大规模数据分布存储在由大量机器组成的集群中，同时集群本身可以由大量成本较低的计算机组成，而不用购置高配置的机器，这很大程度上是一种资源的节约。Hadoop作为一种主流的云计算平台被人们广泛关注，其自身方便而简洁的特点，使得用户编写代码能够得心应手。它的这种明显的优势使得大规模XML关键字查询所面临的问题得到解决。
　　本文针对XML关键字查询相关算法进行了深入研究，并用Hadoop作为计算平台，提出将查询算法并行化的方案，主要研究工作如下：
　　(1)针对目前XML关键字查询算法存在的问题，本文根据Dewey编码分布特点提出了一种智能分组方案，在查询开始之前对 Dewey码集合中的元素进行分组。该分组方案在基于索引搜索算法的基础上设计，并提出了智能分组索引查询算法(Intelligent Indexed Lookup Eager, IILE)。对比实验的结果表明，提出的智能分组索引查询算法获得了较高的执行效率。
　　(2)考虑到目前海量数据在单机上的运行时间过长的问题和大规模数据的处理要求，以及Hadoop环境对数据的分块机制，本文进一步分析了IILE算法的特点，提出了一个基于SLCA分解规律与合并规律的属性，该属性有利于将算法进行分布式计算，并在此基础上提出了一种XML关键字并行化查询方案。该方案基于MapReduce编程模型设计和实现。实验结果表明，对于大规模的 XML关键字查询，提出的并行化方案在Hadoop平台下具有较高的执行效率。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 课题背景与研究意义

1.2 国内外研究现状

1.3 论文研究内容

1.4 论文组织结构

2 云计算平台与相关算法简介

2.1 开源云计算平台Hadoop简介

2.2 XML简介

2.3 本章小结

3 基于智能分组的XML关键字查询算法

3.1 引言

3.2 基于SLCA查询语义的经典算法

3.3 智能分组策略

3.4 基于智能分组的索引搜索算法

3.5 实验及结果分析

3.6 本章小结

4 MapReduce集群下XML关键字查询技术

4.1 引言

4.2 MapReduce SLCA流程描述

4.3 集群下XML的关键字查询

4.4 实验及结果分析

4.5 本章小结

5 结论与展望

参考文献

攻读硕士学位期间发表学术论文情况

致谢