随着互联网的发展,信息呈爆炸式的增长。Web网页在全球范围的使用使得半结构化数据变得越来越普遍也越来越重要。我们可以通过互联网从世界各地接收和发送信息,然而,信息交互的过程中遇到了一个突出的问题：不同的平台用到的数据格式可能是各种各样的,也就是数据格式的异构性问题。传统的关系型数据库在处理这些问题时捉襟见肘,XML就是在这种情况下发展起来的,它为这一问题的解决提供了理论和技术支持。随着XML作为半结构化的标准,它被广泛的应用于Web中的数据交换、网上书店的数据存储、各种配置文件以及电子商务等领域。XML技术在IT环境中扮演着越来越重要的角色,已逐渐成为互联网上传递和交换信息的事实标准。由于大数据时代的到来,XML数据呈几何级的增长,如何在庞大的数据中快速的获得需要的信息变得至关重要。越来越多的人在研究XML的查询方式,更高效率、更大吞吐量的XML查询方法的研究显得越发重要和迫切,并行查询方式走进了人们的视野。XML查询分为两大类,一类是基于图模型的查询,另一类是基于树模型的查询。而基于树模型的查询是现今研究最多的一种查询。树模型的基础是LCA,即最紧致片段。基于LCA有各种各样的查询方式,如基于结果集的查询,基于语义的查询等等,它们都是通过提出新的算法或者改善已有算法使查询结果更全、更快、更符合用户的意图。利用并行技术优化查询的方法是指通过当前硬件具有强大的通用并行计算能力来支持XML查询,这种方法的研究目前还很少见到,具有较大的研究价值和发展前景。最新的研究方向有XML数据库并行查询,或者将不同的XML片段存储在分布式网络,并行的处理这些片段。而本文是分析LCA文档树本身所具有的性质,提出两两分组的并行理念。随着GPU技术的迅速发展,特别是GPU通用计算(GPGPU)的提出和应用,GPU以其高度并行的特性正在高性能计算领域发挥着巨大作用。因此,基于GPU的并行优化技术也逐渐成为研究的热点。鉴于以上两点,本文结合XML查询技术和GPU并行计算,提高XML查询效率。提出了改进的,可以并行的LCA算法。为了实现该算法,首先,由于XML文档结构的独特性,我们需要对每一个XML结点进行编码,我们要求该编码不仅能够唯一标识每一个结点,而且还能表示出结点与结点之间的结构关系。因此,本文选取Dewey编码对XML文档进行编码。在表示XML文档的同时,还能够完成一些简单的结点间运算。其次,XML文档树中具有相同结点名的编码,利用B+树索引,编码字符串比较后,按升序排列存储。因此需要一个适合的容器工具来存放它们。本文采用了嵌入式数据库Berkeley DB来实现,它使得索引与应用程序运行于同样的地址空间中,消除了与客户机服务器配置相关的开销,并且应用程序不需要事先同数据库服务建立起网络连接,而是通过内嵌在程序中的Berkeley DB函数库来完成对数据的保存、查询、修改和删除等操作。在实验过程中可以忽略获取索引的时间,从而削弱了索引对实验主体的负面影响。在算法方面,首先,本文通过XML文档树的特点,提出了一种新的方法,同一个关键字的编码列只需扫描,提高了LCA方法查询的效率。其次,通过XML文档树的特点,提出两两分组的并行策略,并证明了这种策略的可行性。为了证明该算法的可行性,本文主要从查询加速比和查询时间两个方面进行了对比实验。实验数据表明,我们的并行模型比基于CPU串行方式进行的XML查询模型有更好的加速比和更高的吞吐量。