论文部分内容阅读
近年来，大图数据特别是数十亿顶点规模的图数据大量涌现，这一趋势对图数据管理领域提出了全新挑战。图的存储方式直接决定了图数据的访问效率、图查询与挖掘的效率。如何采用合适的划分方法处理大图数据，并能高效的存储和进行图运算，成为大规模图数据库领域需要迫切解决的问题。目前来看，大图存储的基本框架是分布式存储。图划分理论与方法，为解决该问题提供了有效途径。但是面对图数据库海量特点和分布式处理的日益复杂，现有的图划分模型和方法还存在一些不足。本文针对这些问题进行了研究和实验，设计了基于启发策略的图数据流划分算法，能够以较小的时间开销获得较理想的划分结果。主要工作包括以下几个方面：首先，介绍了当前图数据库的发展状况和图数据分区的的研究背景及意义，分析了该领域在国内外的研究现状，讨论了几类图划分模型的定义，并对目前图划分方法进行了总结和分析。主要包括：网格划分方法，谱聚类划分方法，启发式划分方法，多层划分方法等。其次，介绍了图数据流所涉及的概念，定义了图数据流划分的模型和分区启发函数策略，给出了针对图文件和RDF文件的图数据流划分算法和实现过程。最后，通过对几个真实RDF数据集的划分实验，并与METIS(一种多层次的图划分算法)方法和哈希分区方法做了实验数据对比，验证了图数据流划分算法的有效性。实验结果表明，图数据流启发划分算法相比传统的哈希分区方法，能有效地减少边割数量和通信交互，提高了图算法的性能;相比METIS方法减少了分区处理函数的时间消耗，并能更好的适用于大图数据库和增量图数据库。