Web数据管理中的分布式图数据存储和查询

摘要

随着万维网(WorldWideWeb,WEB或WWW)规模和应用的飞速发展,Web数据爆炸式增长,Web数据已经形成了世界上最庞大的数据库。此外,Web数据的相关数据如搜索记录、各种Web服务使用记录数据等都在迅速增长。与传统的数据相比,Web数据具有非结构化,增长速度快以及数据类型多样的特点,这使得Web数据的处理方式和现有的数据处理方式存在着较大的区别。在现实的各个领域中,Web数据处理技术有着广泛的需求和应用,因此对于Web数据的研究已经成为当今计算机科学的一个重点。
　　 为此,我们介绍了CWI[1],一种新的海量数据查询和存储工具。在CWI的实际应用中,需要对大量的Web数据进行存储和索引,并且在此基础上实现关键字和结构信息的查询。TLGM[2]和TLGM-QL[3]作为CWI的一部分,满足了上述要求。本文主要着重于在分布式的环境下实现TLGM数据模型的存储,并且实现了TLGM-QL的四个基本算子。在设计和实现过程中,我们发现真实环境数据的不均衡性会导致存储和查询算法的退化,从而降低效率。针对这些问题,本文提出了一系列均衡措施,保证各节点的运算和存储负载差异保持在一个合理的范围之内。在此基础上,本文提出了新的子图重构的算法,以支持对于图结构的查询,并通过均衡措施保证算法的效率。本文通过对虚拟数据和真实环境数据的实验验证了系统的有效性。
　　 本文的贡献和创新之处总结如下:
　　 1.本文分析了Web数据的特性,并引入了TLGM模型来说明图数据在存储、索引和查询方面和传统数据的区别。本文首先在集中式的环境下分析了使用关系数据库存储图数据的可能性,收集整理了若干图数据,并且设计了一系列的查询,通过实验来验证该条件下图数据存储和查询的效率,由此说明集中式存储的不足和局限性。
　　 2.分析了TLGM的特性,从而阐述在分布式环境下实现该数据模型存储和查询的实现方法。在此基础上,我们概括了TLGM图数据模型可以满足的各类查询条件,并在此基础上提出了四个基本的算子,并举例说明这些算子具有良好的扩展性。同时我们给出在分布式环境下这些算子的实现方法以及具体算法。
　　 3.提出了新的图重构的算法,介绍了如何使用该算法来实现对于图结构的查询。本文通过MapReduce[4]框架来实现该算法,该算法具有良好的可扩展性,并允许我们缓存重构的结果从而提高效率。在实现过程中,我们发现不同数据节点负载差异较大,从而通过对原算法进行若干修改从而达到负载均衡。同时我们生成并收集了若干图数据,并且通过一系列的实验来验证该方法的有效性。
　　 综上所述,我们整理并分析了Web数据存储、索引和查询中的问题,并且通过TLGM模型将此转化为图数据存储、索引和查询的问题。并根据实验结果我们确定了以MapReduce的分布式框架作为基础,在此之上设计并实现了图数据的四个基本算子和图重构算法,通过实验证明了我们的研究成果具有良好的效率和扩展性。