蒋 林，冯 茹，邓军勇，李远成

(1.西安科技大学 计算机科学与技术学院，陕西 西安 710600；2.西安邮电大学 电子工程学院，陕西 西安 710121)

图因其宜于表征不同实体间复杂的依赖关系而受到广泛应用[1-3]。社交网络分析[4]、推荐系统、交通网络等都紧密依赖于高性能、高能效的图计算系统[5-6]。然而，由于真实图规模的不断增加和图结构数据的复杂多变性，图算法变得越来越重要[7]，使得其在遍历、查找等图计算过程中面临巨大的挑战。因此，学术界和工业界非常重视图数据的分析和预处理[8-9]，其中设计数据的压缩格式是常用的重要手段之一。但是，不同的压缩格式对图算法会产生不同的影响，针对特定的图算法，如何根据其性能需求选择合适的压缩格式是一个待研究的问题。

目前，图数据基本表示格式主要有边阵列(Edge Array)和邻接表(Adjacent List)两种。以边阵列的方式存储，可以顺序地读取图数据中边的属性，能有效提高其访存效率。很多系统[10-13]都采用此表示格式来存储数据。邻接表存储方式将源顶点和目标顶点之间的有向边编码为非零项，可线性顺序地访问每一个顶点的所有边信息，有效减少了随机访问，从而提高内存访问速度，目前邻接表是大多数图计算系统[14-16]存储数据的选择方式。然而，对于大规模图进行计算时，传统的图数据存储格式限制了内存访问的速率。同时，因为真实图数据的稀疏性和幂律性等特征，大多数的图计算系统和加速器都会根据系统的特性以及存储的特性，重新设计数据的存储格式，以满足图计算系统的访存、特性，提高内存访问效率。……