基于单机的图处理系统具有较高的性能价格比和潜在的可扩展性,因此具有广阔的应用前景。然而,大规模图处理面临着数据局部性差、访存计算比高、数据高度不规则等问题。由于图数据规模的不断增长,这些问题在单机上基于外存的场景下显得尤为突出。一方面,一些基础的图算法在大规模图数据集上较难做到高效率地实现;另一方面,提供通用接口的图处理系统往往存在I/O效率不高、收敛速度较慢等问题。因此,本文从典型的图遍历算法BFS入手,结合现实世界图数据的特点和存储设备的特性,对该算法进行了优化;进一步地,对通用图系统中数据I/O、图数据划分和一致性策略等方面进行了研究。本文的创新点主要有:·单机上社交图数据的快速广度优先搜索方法FastBFS。通过分析大规模社交图数据的特点,充分利用BFS算法在数据访问过程中的特性,加速单机上的广度优先搜索过程。采用以边为中心的图处理策略来提高外存访问的带宽,同时降低图划分和重新组织的开销。提出基于异步I/O的删边机制,删除与后续计算无关的边来有效地减小遍历过程中的数据量。此外,通过高效地调度I/O数据流,Fast BFS可以使用多块磁盘来提高I/O并行度,从而加速计算。实验结果表明,Fast BFS在计算性能上最高可以达到单机外存图处理系统X-Stream和Graph Chi的2.1和3.9倍。·单机上Web图数据的快速广度优先搜索方法Fast BFS+。针对Web图等直径较长的图数据的特性,提出高效灵活的图遍历方法Fast BFS+。引入跨迭代的异步删边机制,提高处理效率。提出动态的删边机制,通过设置阈值的方法动态开关删边机制,从而大幅度降低在Web图数据上由删边所引入的开销。实验结果表明,Fast BFS+能够在Web图数据上获得良好的性能,执行速度与X-Stream和Graph Chi相比达到数倍的提升。·单机上基于非对称二维分区的异步图处理方法Async Stripe。提出二维非对称的图划分方法,兼顾数据访问的局部性和计算调度时的高效性。利用基于条带的数据访问策略,获得较高的磁盘访问带宽和更小的I/O访问数据量。同时,Async Stripe还支持两种异步一致性策略,异步地执行不同类型的图算法,大幅度加快收敛速度。实验结果表明,对于典型的遍历算法和稀疏矩阵乘法算法,Async Stripe的性能优于X-Stream和Grid Graph等典型系统。