论文部分内容阅读
图是一种较为复杂的数据模型。与线性表和树相比,图能表达更多种类的信息。现实生活中很多场景都能用图表示,如最短路径的生成,疾病的传播,参考文献的引用等。图也能用来表示一些新型的模型,如网页链接关系,蛋白质分子的组成, RDF数据分析,社交网络分析等。随着互联网技术的发展,图数据的规模也呈爆炸式增长。由于存储和处理的局限性,传统的图数据管理系统已经很难解决大规模图数据的存储、查找、计算和更新的问题。因此,设计一种紧凑而高效的图数据处理系统成为人们亟待解决的问题。 以路径为中心的大规模图数据处理系统(TripleGraph),提出一种高效处理十亿级别图数据的技术。这种技术根据图数据的关联关系,采用树型结构对图进行抽象。为了减少图数据的存储空间,TripleGraph设计一种紧凑的存储结构。针对边集合进行按行压缩的方式,每一行的行ID只存储一次,行内的边集合采用增量变长整型压缩。为提高压缩性能,TripleGraph在预处理时对所有节点进行改进的深度优先分配ID策略,以保证相关联的节点具有相近的ID。在每一个存储块内,不同行的节点和边权重分别集中存储,以保证在数据更新时具有局部性和顺序性。在迭代计算方面, TripleGraph提出以路径为中心的大规模图数据处理方法。因此大部分情况下的计算都是顺序访问存储介质而不是随机访问。每一次迭代更新图的不同部分,这种策略在定义和执行图的局部性更新上有很好的收敛性。TripleGraph一方面发挥存储上的优势极大地减小了I/O的开销,提高了顺序读取数据的概率;另一方面采用线程窃取调度的策略,实现了处理器的负载均衡,减小了“木桶效应”。 TripleGraph通过对十亿级别的图数据在多种算法上的存储性能和速度性能上的测试,该方法在存储空间上比系统GraphChi至少降低了29%,在PageRank执行性能上比GraphChi至少提升7.6倍。实验表明TripleGraph在存储和迭代计算上均具有较好的性能。