图由于自身的结构特征，可以很好地表示事物之间的关系。图中点和边的强关联性，需要图数据处理系统对图数据进行一系列的操作，包括图数据的存储、图查询、最短路径查询、关键字查询、图模式挖掘以及图数据的分类、聚类等。随着图中结点和边数增大到几千万甚至上亿，图数据处理的复杂性给图数据处理提出了挑战。

图数据中主要包括图中的结点以及连接结点的边，通常具有三个特征。

1）结点之间的关联性。图中边的数量是结点数量的指数倍，因此结点和关系信息同等重要。图结构的差异也是由于对边做了限制。在图中，顶点和边实例化构成各种类型的图，如标签图、属性图、语义图以及特征图等。

2）图数据的种类繁多。在许多领域中使用图来表示该领域的数据，如生物、化学、计算机视觉、模式识别、信息检索、社会网络、知识发现、动态网络交通、语义网、情报分析等。每个领域对图数据的处理需求不同，因此没有一个通用的图数据处理系统能满足所有领域的需求。

3）图数据计算的强耦合性。在图中，数据之间是相互关联的。因此，对图数据的计算也是相互关联的。这种数据耦合的特性对图的规模日益增大，达到上百万甚至上亿结点的大图数据计算提出了巨大的挑战。

大图数据无法使用单台通用机器进行处理，但如果对大图数据进行并行处理，对于每一个顶点之间都是连通的图来讲，难以分割成若干完全独立的子图进行独立的并行处理。即使可以分割，也会面临并行机器的协同处理以及将最后的处理结果进行合并等一系列问题。这需要图数据处理系统选取合适的图分割以及图计算模型来迎接挑战并解决问题。(www.daowen.com)

Google的Pregel系统是一个典型的图数据处理系统。Pregel是Google提出的基于BSP（Bulk Synchronous Parallel）模型的分布式图计算框架，主要用于图遍历（BFS）、最短路径（SSSP）、PageRank计算等。BSP模型是并行计算模型中的经典模型，采用的是“计算—通信—同步”的模式。它将计算分成一系列超步的迭代。从纵向上看，它是一个串行模式。而从横向上看，它是一个并行的模式。每两个超步之间设置一个栅栏，即整体同步点，确定所有并行的计算都完成后再启动下一轮超步。Pregel的设计思路是以结点为中心计算。结点有两种状态：活跃和不活跃。初始时每个结点都处于活跃状态，完成计算后每个结点主动进入不活跃状态。如果接收到信息，则结点被激活。没有活跃结点和信息时，整个算法结束。

Pregel架构有三个主要特征：

1）采用主/从（Master/Slave）结构来实现整体功能。一个结点为Master，负责对整个图结构的任务进行切分，根据结点的ID进行散列计算并分配到Slave机器。Slave机器进行独立的超步计算，并将结果返回给Master。

2）有很好的容错机制。Pregel通过Checkpoint机制实行容错，结点向Master汇报“心跳”维持状态，结点间采用异步信息传输。

3）使用GFS或BigTable作为持久性的存储。Apache根据Google于2010年发表的Pregel论文开发了高可扩展的迭代的图处理系统Giraph，现在已经被Facebook用于分析社交网络中用户间的关系图中。