论文部分内容阅读
随着社交网络的发展,每天都在产生大量的数据,而这些数据区别于关系型数据,具有网络的特性,这些数据构成了大量的图数据。传统的单机处理图数据的方式已经不能适用于现有环境,因此,我们需要使用分割算法将图数据分割成小块再进行下一步的处理,这种处理图数据方式的要点在于如何将图划分成子图分布到集群上,如果划分不当就会造成子图之间大量的通信开销。传统的图数据分割算法在启发式和多层划分方面来说有很多优秀的算法,这些算法可以解决一些小型数据的划分,在大规模数据划分上,多层划分的一些算法的支持力度较大。然而,传统的分割算法对于实时变化的图数据并不能做出很好的处理,它们往往并未考虑到图数据的改变对整个划分结果的影响,也无法对图数据的增删改进行处理。而动态图数据应用十分广泛,因此,研究一个支持动态分割的图数据系统很重要。 针对上述问题,本文对大规模动态图数据上的划分问题进行研究,根据图结构性质及动态图特点,提出并实现了一种基于邻域的动态图分割算法。算法分为静态切分和动态调整两个阶段,其中基于割边算法整合现有优秀的多层划分算法提出了大规模图数据的静态切割算法。在优化后的静态切割算法的基础上,根据图数据的动态扩张的特性提出动态分割算法。根据迁移顶点所达到的最小负载值进行顶点迁移,并在此基础上进行性能及割边控制优化操作。在完成切分的基础上,对于划分完的子图的存储提出自己的一些存储方案。本文将提出的算法在各类图数据集上进行了验证,验证的结果显示在平衡度和割边等指标上优化后的算法效果显著,提高了划分的合理性,并且在保证割边不增加的情况下提高了图分割的平衡度,使得集群负载均衡。