图数据压缩格式对广度优先搜索算法影响的特性化分析

任 含，邓军勇

(西安邮电大学 电子工程学院 陕西 西安 710121)

0 引 言

在当前信息化时代，随着物联网和云计算的日益发展，生物医学、网络社交、网络信息追踪等许多领域内的数据信息量呈指数增长，并且越来越多的信息被连接起来，以图形形式存储在各个领域[1-2]。由于这些数据信息规模和计算的日益复杂化，给现代图处理系统提出了巨大的挑战。图计算是处理各种数据信息的常用手段之一[3-5]，不同压缩格式的数据信息会对图计算问题产生不同的影响，如何选择合适的图数据压缩格式以达到最佳性能需求是一个不可避免的问题。

图可以表示不同实体间复杂的依赖关系[6-7]。图数据可以由不同的压缩格式来表示，不同的图数据压缩格式有不同的表示和复杂度。当前很多研究采用不同的图算法解决方案来提高图数据处理时的性能和效率，但是由于图算法的性能效率由不同图数据压缩格式中边和顶点的处理来确定，在执行过程中，程序的行为不仅会随时间变化而变化，更重要的是不同的图数据压缩格式复杂度会对图算法处理产生不同的影响，因此有效地应用图算法是一项艰巨的任务[8-9]。所以在图算法中如何快速选择合适的数据压缩格式以达到预期的最佳性能是本文的一个重要研究问题[10]。本文针对BFS算法处理不同压缩格式图数据时的性能指标进行特性化分析，为不同条件下应该选择不同压缩格式的数据集提供了依据。……