图数据库发展
本文大部分文本（90%）来自《CCF2014-2015中国计算机科学技术发展报告》，互联网上无电子版，由本人进行OCR并粗略校验。
1. 引言
随着社交网络分析、Web语义分析、生物信息网络分析以及交通导航等新兴应用的快速增长，不同领域出现了规模庞大、内部结构复杂、查询需求多样的大图数据。2015年最新公布的统计数据显示，全球最大的社交网络 Facebook拥有14.15亿月活跃用户。用户之间的好友关系超过2000亿条边，日均记录分享量也达到了数十亿级别，65%以上用户为日活跃用户;国内领先的QQ社交网站注册用户为也超过了8.29亿。
不同领域大图数据应用过程中存在通用的数据操作。例如，在社交网络中，发现影响力最大的用户，能够更加有效地推送广告;在交通网络中，发现两点间满足不同标准的路径，有助于客户行程规划;在金融交易网络中，发现特定的模式，有助于发现异常的交易行为;在社交网络中，发现关联关系密切、特征相近的用户群体，有助于商品的销售。这些大图数据操作不仅仅涉及数据节点自身的信息，而且涉及数据节点之间的结构关系。我们可以将大图数据操作抽象为获取特定节点、获取特定路径、获取特定子图等，通过实现这些通用操作，构建大图数据管理系统。
图数据管理在数据库领域是一个经典的研究问题，其研究历史呈现一个波浪式前进的过程。早在20世纪70年代，由于图数据模型表达能力强，数据管理领域的研究人员就提出图模型对客观世界的数据进行建模，并设计了相关的图数据管理原型系统。Charles W. Bachman还由于其在图数据模型方面的贡献于1973年获得图灵奖。之后，由于图数据查询在表达和执行方面的复杂度都很高，图数据管理系统在应用方面存在挑战，研究趋缓。在这一阶段，关系数据库由于其操作接口简单，查询优化技术实现突破，逐渐成为数据管理中的主流。2000年之后，随着社交网络等真实大图数据的迅猛增长和其上应用需求的推动，图数据的相关研究工作重新成为热点。例如，在VLDB2014国际会议中(http://www.vldb.org)，出现了4个图数据管理的专题讨论。国际T巨头，包括 Google、 Facebook、微软等正在进行分布式大图数据管理系统的研发，支持包括海量Web网页重要性排序、社区发现等操作。
图数据管理也得到计算机方向其他研究领域的关注。例如，在2014年系统软件专委会所撰写的《面向新型计算模型的系统软件研究新进展与趋势》文中，上海交通大学陈海波团队也将《图并行计算系统的研究进展与趋势》作为重要内容进行论述。本报告将侧重从数据管理的角度对大图数据管理的相关技术展开论述。部分关键技术或系统如在《图并行计算系统的研究进展与趋势》论述过，本报告将不再赞述。
2. 大图数据管理面临的挑战
大图数据是大数据的重要形态，具有大数据的4V特性：
- 首先大图数据规模庞大，不仅仅包含大量图数据节点及其节点属性，而且包含图数据节点之间复杂的关联关系;
- 其次，大图数据表达灵活，不同类型节点结构异构，每个节点和边上属性模式信息各不相同，很难抽象出相对固定的模式。例如，在客户购物关系图中，每个客户或者商品的属性不同，客户(或者商品)内部存在关联关系，客户与商品之间也存在关联关系。
- 再次，大图数据处于动态变化中。随着时间不断的变化和演进，大图的内容信息发生变化大图的结构信息也发生变化，如节点/边的新增和删除等。
- 最后，大图数据中也蕴含着丰富的价值，通过分析大图数据中的结构、关系、时序等信息，为不同领域的大图数据应用决策提供支持。
大图数据还具有复杂性C的特性。由于大图数据表达方式灵活，任意数据节点之间都可能存在关联关系，假定节点数量为n，单一类型关联关系最多为n2，多类型关系景下，关联关系就更加丰富。整个大图看作一个复杂网络。大图数据操作往往涉及全局数据，计算代价高。
大图数据的4V+C的特点使得大图数据的管理面临巨大挑战。
第一，大图数据环境中图操作代价高。和传统的关系数据或者XML树状数据相比，图数据缺乏结构约束，操作复杂。以图数据中的两点最短路发现为例，经典 Dijkstra算法的复杂性为0(mnlogn)，其中n是图中的节点数，m是边数。随着图规模的增长，上述操作的代价急剧上升。此外，这一算法复杂性基于单机内存环境。考虑到单机内存无法满足大图数据处理需求，大图数据操作还需要考虑磁盘访问代价和分布式环境中网络访问代价。
第二，大图操作需求灵活，提供简洁、高效、表达能力强的查询语言面临困难。随着大图数据应用的深化，大图数据之上的操作需求日益复杂。大图数据操作不仅仅局限于类似检索某个点的所有关联边这样简单的查询，而且还包括更加复杂的、侧重于全局的查询和分析，如图中最短路发现查询、最小支撑树构建查询、子图模式匹配等操作。考虑到大图数据操作的灵活性，很难抽取公共部分进行优化或者简化表达。此外，图数据操作通常需要循环迭代，这对方便、易用的图查询语言的设计有很大的影响。
第三，大图数据复杂性的特点使得很难直接应用并行计算模型解决大图数据操作。图数据规模庞大使得并行分布策略不可避免。同时，由于图数据内部关联灵活、复杂，图数据操作很可能需要全局的图数据信息。即使实现图数据的分块和并行操作，不同分块之间依然存在大量的访问，无法简单直接实施并行操作。
3. 大图数据管理中的主要研究问题
面对大图数据管理的挑战，很多研究机构从不同的角度展开研究工作，包括大图数据管理的体系结构、大图数据的组织、大图数据管理的查询设计、大图数据查询执行和优化等问题。
3.1 大图数据管理的体系结构
在大图数据管理中，不同的底层体系结构、底层系统软件、硬件都会对大图数据管理产生影响。
分布式大图数据管理是大图数据管理的主流结构。由于大图数据的规模庞大、节点信息丰富、计算代价高，利用多机的计算资源和存储资源管理大图是大图数据管理的趋势。在分布式大图数据管理中，目前应用比较广泛的是基于 Mapreduce和基于BSP计算模型的大图数据管理。基于 Mapreduce框架实现大图数据管理是可行的技术路线。 Mapreduce框架是目前通用大数据的并行处理框架，大图数据的查询可以通过 Mapreduce框架实现，具有良好的可扩展性和大数据分析的高吞吐量。但是，由于 Mapreduce框架处理大图数据导致过多的磁盘读写操作，基于 Mapreduce框架的大图数据管理效率不高。
基于BSP计算模型的大图数据管理方案具有较好的可扩展性和较高的效率。为了克服 Mapreduce管理大图导致的各类问题， Google借鉴BSP计算模型的思路，设计了Pregel框架。 Pregel框架将图数据存储在分布式环境中不同计算节点的内存中，支持以点为中心的计算模式，通过内存随机访问直接修改节点的状态，避免磁盘读写的/O代价。Google的 Pregel系统已经用于Web级别的大图节点重要性排序等操作，展示出较强的可扩展性。 Pregel在 Apache社区的开源版本Giraph在 Facebook也得到重要应用，在社区发现、子图聚类等操作上取得良好效果。
单机大图数据处理是一种重要的技术路线。随着CPU和内存技术的发展，使得单机有资源支持海量大图的处理。单机环境中无需考虑分布式大图数据管理中引入的网络代价，其算法设计实现简单，调试安装代价相对低廉。为了提高大图数据处理的可扩展性，而单机内存有限，单机计算环境中使用外存不可避免，单机大图数据处理框架的一个关键问题就是需要降低外存随机扫描对大图数据操作的影响。目前单机大图数据计算框架，如GraphChi、 XStream等，处理常用的测试图数据(如 Twitter数据)，能够取得和分布式大图数据计算框架可比较的性能。
基于关系数据库管理大图数据是另一种可选的技术方案。关系数据库在联机事务处理领域取得巨大成功，成为企业信息基础设施中不可或缺的组成部分，有巨大的市场份额。图数据管理和关系数据管理也有很多相通之处，如都需要数据存储、数据缓存、索引、查询优化、并发控制等。基于关系数据库能够快速实现超过内存的大图数据的管理，如索引、更新、并发操作等。关系数据库管理图数据面临的问题是关系数据库擅长一次处理一个集合，而图数据操作考虑优化策略，往往采用一次一个节点的操作方式，直接利用关系数据库管理大图数据效率不高。
充分利用新硬件的特性是提高图数据管理系统性能的有效手段。CPU中 Cache是影响计算性能的重要因素。在图数据组织和操作过程中考虑Cache的特寺性，提升CPU的Cache命中率，能够在全内存环境中进一步提高系统性能。图形处理器GPU带有大量的并行计算模块，通过设计合适的图数据分块和并行方法，结合CPU和GPU提高大图数据管理的效率。相对于带有机械设备的硬盘，采用电子寻址的闪存更加适合支持带有大量随机访问的图数据操作。在基于闪存的图数据管理中，需要考虑闪存写入代价昂贵的约束。
3.2查询语言设计
图数据表示方式灵活，查询分析形式多样。图数据查询不仅仅包括对特定子图数据的获取，而且包括图数据的转换。由于查询方式多样，目前没有一种广为接受、易于表达、便于优化支持高效执行的查询语言。我们分析图数据管理中可能的查询语言方式。
提供图数据基本操作API是目前大图数据管理系统的一种查询方式。目前的图数据库管理系统，如Neo4j，提供了基本的图操作APl，如图数据存储、遍历、最短路查询等操作。用户在其应用程序中仅仅需要调用这些AP，系统负责这些调用的执行和优化。然而由于图的操作方式灵活，利用有限的API操作很难支持不同领域的图操作需求。例如，Neo4j无法直接实现 Page Rank的迭代计算。
根据现有图数据管理框架的接口要求，编写图数据不同查询脚本是目前图数据查询和分析的主流方式。系统不提供相对高层的图操作API，而是提供相对底层的编程接口。如Mapreduce框架接口、以点(边)为中心的计算接口等。用户根据查询流程，编写符合接口的查询脚本。这种方式足够灵活，能够支持复杂的图查询操作。但是，这种方式需要用户掌握脚本语言，负责脚本的编写、调试、优化等，用户应用开发负担重。
提供描述性图查询是介于图操作API和图框架接口的一种方式。类似于关系代数，代数将不同类型的图操作公共部分抽取出来，形成图数据操作体系。用户通过相对高层的描述性查询表达图操作，系统负责将这些查询转换到底层框架中。这种方式能够屏蔽不同的底层平台的实现细节，减少用户应用系统实现的代价。然而，由于图操作本身的复杂性，即使采用描述性查询，描述性查询自身也很复杂，例如，描述性图查询中需要有递归或者迭代机制，还需要选择、赋值等操作。
图的关键字查询是图数据查询的一种有前景的查询方式。图数据具有灵活的结构特性，用户通过结构信息表达查询繁琐。而现实中图数据是带有其他属性信息的。用户可以采用关键字描述图查询目标，图查询反馈包含这些关键字的特定子图，图的结构信息用于查询结果的排序。采用这种方式无需用户了解复杂的图结构，极大减轻用户图查询的代价，但是不支持图数据的抽取和转换。
面向特定领域的图查询也是一种有效的图数据查询方式。特定领域的需求实际上是图数据查询的一种约束和限制。比较典型的领域相关查询语言是知识图谱领域中的SPAROL。 SPARQL采用类SQL查询的形式表达查询模式，查询结果为与查询模式匹配的数据子图。 SPARQL采用类SQL的形式，能够降低用户的学习成本，提高用户的接受度。
3.3 大图数据组织
大图数据管理需要根据所在的计算环境，合理组织数据，提高数据处理的效率。在分布式环境中，大图数据需要划分到不同的计算节点中进行保存和处理。图数据划分需要考虑不同图划分之间的消息通信、计算节点的负载平衡等因素。最原始的图划分方法采用随机节点分块方法，根据Hash函数将图节点划分到不同的分区块中，或者采用节点ID区间的方式进行划分。由于不同子图之间的边意味着消息通信量，可以采用目前综合性能优异的 Metis图划分方法，获得降低子图间通信量的图划分方法。由于同一数据节点在计算节点中出现并且仅出现一次，这种划分策略又称为点划分策略。
针对度数分布符合幂律分布的图数据，可以采用边划分的策略。即选择度数较大的数据节点进行切分，建立这一个数据节点在不同的计算节点中的副本，分散存储相关联的数据边，利用副本之间少量的消息量，降低点划分形成的子图间消息数量，减少采用点划分导致的计算负载不均衡的问题，提高整体运行效率。
现有系统还采用了以边为中心的计算模式。通常来讲，图中边的数量远大于点的数量，而边的信息在图数据操作中往往是无需改变的，点上附加的数据值是需要频繁改变的。以边为中心的思想将节点信息和边信息进行分离，将边的信息置于外存，节点信息尽量置于内存，通过顺序扫描边，改变内存中节点的数值。由于处理脚本主要是改变节点的数据值，这种方式本质上也是一种以节点为中心的计算。
在单机外存环境中，图数据划分内部还需要进一步组织，减少外存随机扫描对查询效率的影响。例如，按照边某一端点的ID实现图数据的顺序划分，而在同一个划分内部，按照另一端点的DD进行了排序。这种组织方式能够在某一个图划分加载到内存时，通过顺序扫描特定的划分片段可以获取这一图划分相关边信息，减少外存随机访问的影响。
3.4 大图数据查询分析的执行和优化
目前分布式大图数据操作执行方式分为同步执行方式和异步执行方式。在同步执行式中，同一个计算任务由多个超步组成。在每个超步中，节点接收到其他节点发送的消息，根据用户脚本处理消息，向其他节点发送消息。每个超步间通过栅栏保持同步，超步结束需要等待所有的参与计算节点结束。同步执行方式的优势为编程易于调试，系统稳定性高，可扩展性高。
与同步方式对应的执行方式为异步执行方式。其特点是执行过程中没有全局统一的同步概念。主要思路为数据节点在任何时刻，都可以进行计算。异步的方式优势在于能够快速收敛，执行效率较高。但是，异步执行方式无法保证执行过程中的确定性。即同一任务多次执行，最终结果可能都不一样。这一特点在某些数据操作中影响计算有效性，并使得算法在分布式环境中难以调试。
减少分布式环境中通信量是大图数据操作的一种优化策略。传统以节点为中心的计算模式中，不同数据节点之间通过消息或者共享内存进行通信。如果能够感知到同一计算节点的其他数据节点，则可以通过效率较高的局部内存访问替代昂贵的网络访问。良好的图划分方法是实现这一优化的基础。
负载平衡是分布式查询执行过程中需要考虑的问题。分布式环境中同步执行查询的代价取决于最慢的计算节点。不同类型的图数据查询产生不同的负载分布。根据计算节点的实时负载，迁移数据节点，实现负载的动态平衡，能够查询的运行时间。在数据节点的动态迁移过程中，需要考虑数据节点在分布式环境中的重定位问题。
查询脚本层面的优化是大图查询优化的有效手段。图数据操作通常涉及循环迭代而在分布式系统中每次循环都有额外代价，如BSP模型中超步的同步代价、 Mapreduce框架中图数据的扫描和传输等。此外，某些循环在分布式环境中活跃节点过少，循环带来的相对收益差。减少分布式环境中的循环次数是图数据查询重要的优化策略。
4. 国外研究现状
面对大图数据带来的技术挑战，国外高校、研究机构展开大图数据的研究工作，设计并实现了大图数据管理系统。我们以典型系统为代表，分析国外大图数据管理相关的研究进展。
4.1 大图数据分布式管理框架
Pregel： Pregel是Google在2010年发表针对大图数据的分布式计算框架，是目前大图数据管理领域最有影响力的研究成果之一。针对 Mapreduce框架管理大图缺乏迭代支持、随机数据修改代价昂贵等问题， Pregel框架做了创新和优化。 Pregel将不同数据节点进行分割，分别加载到不同的计算节点中。图数据查询整体遵循BSP计算模型，每个图查询由多个超步加以完成。每个超步中，图数据节点计算采用以节点为中心的编程模型。 Pregel框架在 google得到广泛应用，支持Web级别的大图数据节点重要性排序等基本操作。
Giraph： Giraph 是 Apache所支持的，它是一个在 Hadoop之上运行的 Pregel的开源系统。 Giraph 中实现了BSP的计算模型，支持用户以点为中心的脚本编程。相对于其他分布式图查询系统， Giraph 有一个显著特点，即 Giraph 本身是一个无 Reducer的 Mapreduce任务，图数据查询处理易于和 Hadoop环境进行集成。 Giraph 在 Facebook有重要的应用，支持社区发现、节点重要性排序等操作。
Trinity系统： 微软研究院设计了Trinity系统。该系统能够同时支持低延迟的在线查和高吞吐量的离线分析。为了避免外存随机扫描的影响， Trinity将图数据保存在内存云中，并且设计了复杂的内存机制来管理边长数据。 Trinity在上层引入了查询语言TQL表达图数据的查询。
Graphlab 和 PowerGraph： Graphlab是一个支持异步执行方式、利用共享内存的大图数据管理框架。为了提高异步执行中的数据一致性， Graphlab引入了数据节点访问的锁机制。针对自然图中高度数节点带来的负载偏斜， Graphlab的后续版本 PowerGraph引入了边划分的策略，建立高度数节点的副本，划分关联边到不同的计算节点，使得每个算节点上拥有均衡数量的边，从而提高查询执行效率。
4.2 大图数据单机管理框架
GraphChi和 XStream： Graphchi是单机图数据查询框架。单机环境处理大图不可避免需要外存的支持，而大量随机访问外存数据会产生严重的性能问题。 Graphchi将图数据按照节点ID区间进行划分，保存入边信息，每个分区的出边信息在其他分区中顺序存储，这样利用外存的顺序访问替代随机方法，提升单机外存环境中以点为中心的计算框架的性能。 Xstream采用以边为中心的存储方式，不需要对边表进行排序，也不需要索引，同时通过顺序存取提高缓存的命中率。
4.3 基于关系数据库的大图管理框架
Vertexica： 其是MIT开发的基于关系数据库(列式存储)的图数据管理框架，其特点是基于数据库系统存储图数据，其上提供了以点为中心的计算模式，支持用户通过编写脚本管理图数据;还提供了一种查询语言 GRAPHiQL，支持用户表达关系操作和图数据操作。
4.4大图数据高层查询语言
SociaLite： SociaLite是斯坦福大学开发的一种基于Datalog的大规模图数据查询系统。SociaLite扩展Datalog支持嵌套底层数据，支持递归实现聚集操作，允许用户自定义执行次序等。Sosocialite可以方便表达可达性查询、最短路查询、Pagerank、三角形计算等图查询。用户提交的 Socialite查询能够自动转换到底层执行计划，并实现优化。
4.5 部分大图数据管理框架特性
5. 国内研究现状
下面我们从大图数据管理框架、大图数据操作算法、大图数据应用三个层面讨论国内在大图数据管理方面的进展。
5.1大图数据管理框架
BC-BSP： BC-BSP是东北大学和中国移动合作开发的，基于BSP模型的大图数据布式并行选代计算的平台。BC-BsP系统支持基于虚拟桶的均衡哈希划分、基于边聚簇特性的图划分动态调整策略，提供了以分区(子图)为中心和以(顶)点为中心的两种计算模式和编程接口，提高了数据处理的灵活性和适应性。与目前的开源框架Hama以及Giraph相比，BC-BSP具有良好的可扩展性。
MoCGraph： MoCGraph 是北京大学开发的基于消息流式处理的可扩展大图查询框架，在BSP环境中能够以数据流的方式处理大图计算中的消息数据，减少中间结果对框架内存的压力。同时利用流式计算减少针对外存的随机访问操作。
PSgL： PSgL是北京大学开发的子图并行列举框架，支持在图数据中枚举所有与模式图同构的子图。其利用分治思想，基于图遍历操作迭代枚举结果，设计了多种分发策略保证计算节点间的负载均衡，提出了三种独立机制来缩小中间结果规模，支持索引查询、图结构分析等重要应用。
VENUS： VENUS是华为研究人员所研制的单机大图数据管理框架。VENUS针对GraphChi框架存在的问题进行了优化，分别存储支持更新节点信息和只读边信息，通过顺序扫描减少边数据对内存中的占用，通过将节点数据尽可能放入内存，减少访问节点数据对随机扫描的影响。
GraphHP： GraphHP 是西北工业大学开发的图数据管理框架，结合图查询执行中的同步模式和异步模式。 Graphhp中数据节点分为边界节点和局部节点。在同步环节，边界节点之间进行消息通讯，而局部节点的计算通过异步操作完成。通过两阶段的超步模式加快了系统收敛速度。
Graph Memory： Graph Memory是东北大学开发的图数据存储和查询优化系统，结合集群环境下的异构计算资源(如众核、多处理器、多处理节点等)以及内存访问特性，提供适合大图数据的并行处理框架、分析任务调度策略，以及系统负载平衡算法;采用基于世系的数据容错技术和基于热备进程的任务恢复技术，来提升整个系统的可靠性和可用性。
5.2 大图数据查询和分析
GStore 和 GAnswer： GStore是北京大学开发的利用子图匹配技术面向海量RDF数据的SPARQL检索引擎。gStore将RDF数据存储为图数据，利用图模式匹配操作支持图SPARQL查询，引入结构编码减少模式匹配过程中的搜索空间。gAnswer引入了RDF数据的自然语言查询方式，避免了用户编写复杂的结构查询，利用子图匹配，同时获取自然语言查询答案和短语消岐。
Laft-Suite：Laft-Suite是清华大学研发面向社交网络分析系统，深入解决了社区结构分析、重要节点及潜在重要节点发现、社交链接产生方向腿短、推断以及社交网络演化预测等问题，提供了一系列有效的解决方案，不仅支持传统的社交网静态结构分析，而且能展现社交网络的生成过程和演化规律。
5.3 大图数据应用系统
学术空间( ScholarSpace)： 学术空间是人民大学开发的，以学者为中心的个人学术息空间。支持各领域基于作者名的学术信息查询，自动生成包括发表文献列表、发表数量园线图、合作作者列表/图形化展示及知名学者图片、新闻的个人学术成就总页面。还供了了面向各学科领域的文献发表数量机构排名统计功能和各期刊收录文献单位和作者的Top20排名统计功能，方便用户更直观地了解本领域的学术研究现状。同时系统按月提供所收录刊物的文献导读辑录，方便学者浏览本领域文献。系统通过自主研发的Web数据抽取和数据集成方法构建了语义丰富的关联数据库，目前具有近200万论文实体，100多万作者实体。系统借助RDF通过三元组形式对关联数据进行描述，结构与大图数据十分类似。学术空间 ScholarSpace 采用北京大学 gStore对RDF数据进行存储，包括1000万条三元组、60万节点，其查询引擎通过编码等方式对图的节点和边进行组织，并通过子图匹配算法实现图上的高效查询，具有良好的性能和可扩展性，能够在集群上进行实现，取得了良好的应用效果。
学者网：学者网是华南师范大学开发的，面向学者的社交网络，目前用户及学术数据记录已超过亿条，形成了复杂的图数据模型。基本存储模式采用关系数据库与分布式存储混合方式;对需要频繁读取的数据，实现高效的缓存查询和更新技术;对于需要进行大规模处理的数据，采用离线计算的方式实现;在进行论文搜索、学者关系和学术社区挖掘等推荐系统，采用了 Hadoop分布式框架对数据进行处理。
中国娱乐圈明星关系网： 这是我在做学校大作业时候，自己做的一个使用图数据库的应用，其中数据库使用单机版的Neo4j，节点数量仅仅3000内，覆盖了国内的大多数明星。使用了数据库的最短路等算法，可以验证6度空间理论。查询语言采用了Neo4j自主发明的查询语言cypher。
6. 国内外研究进展比较
面对大图数据管理的迫切需求，从工业界到学术界都开展了图数据管理的研究工作，图数据管理成为国内外的研究热点。国内的研究人员逐渐从大图数据算法研究，扩展到框架实现以及系统应用。我们从大图数据管理的框架层面和算法层面比较国内外的研究进展。
在框架层面，国外研究机构所提出的 Pregel、 Powergraph、 Graphchi等框架在系统成熟度、系统应用、原创性方面，要优于国内高校和科研院所所提到的框架。 Pregel在Google已经成功支持Web级别大图数据操作， Powergraph提供了多种图数据分析挖掘算法， Graphchi在单机上取得集群可比较的性能，上述框架全部开源。国内各个高校和研究机构也在框架层面做了大量的工作，但是更多侧重于现有框架在某些方面的改进，包括消息处理机制、任务调度机制、图数据分割机制、查询优化机制等，期待更多原创性系统性、实用性的成果出现。
在图数据分析算法层面，国内研究结构针对最短路发现、社区发现、 SimRank计算、模式匹配、信息推荐等热点问题，提出了多种图数据分析和挖掘方法，在方法的可扩展性、方法的效率，方法的资源消耗等方面，达到和国外同行所提出的方法相当的水平。
图数据研究的最大推动力是应用的发展。国内社交网络平台数据(如微信)，购物网络平台数据(如淘宝)等发展迅猛，产生了大量的图数据，也带来了现实的挑战。阿里、华为、腾讯、百度等国内巨头已经开始了大图数据管理关键技术的研究和应用。这些基于真实场景和需求的研究更有生命力，将提高国内大图数据管理的研究水平。
7. 总结
随着应用的逐步深化，图数据管理的研究也将继续发展。我们将图数据管理的发展 趋势归纳为以下几点。
兼顾在线查询和离线分析的大图数据管理系统：不同类型的计算任务具有不同的特点，在线应用要求实时性高、响应及时，而离线处理任务更关注任务吞吐量、并发能力以及资源的合理利用性。目前所提出的图数据管理的框架，包括 Pregel、 GraphLab、GraphChi等，更多侧重于图数据的分析，强调图数据分析的吞吐量，查询的实时响应不是目前框架的重点。兼顾查询效率和吞吐量的大图数据管理系统将结合两种处理方式的优点，屏蔽具体的计算模型，根据用户提交的查询和数据量自动选择合适的处理方式。
支持丰富属性的大图数据管理框架：目前的大图数据处理框架，更多侧重于大图数据结构的分析，而现实世界中的大图数据往往带有属性信息。大图数据实际上包含结构和内容两类数据。大图数据之上仅考虑结构特性的查询应用场景较窄。充分借鉴其他研究领域，如信息检索领域、数据挖掘领域的研究进展，实现结构和内容相结合的大图数据查询和分析，为应用提供更有效的大图数据管理服务。
大图数据管理中的事务：随着大图数据应用的不断深入，多个用户可能同时于操作大图数据，同时大图数据是保存在不同的数据中心中，如何支持多个用户并发访问大图数据，保证数据一致性是大图数据后续需要解决的问题。某些最新的工作已经开始探讨分布式大图计算环境中错误恢复等操作，后续还有广阔研究空间。
参考
由于前些年以及后些年的《CCF中国计算机科学技术发展报告》都有电子版，并且大家都可以下载，唯独这年的电子报告无从下载。恰好当年我以学生嘉宾参加CNCC2015，有幸获赠一本《CCF2014-2015中国计算机科学技术发展报告》，并有图领奖 Michael stonebraker的亲笔签名。于是就利用OCR进行了翻译，并人工进行了校验，并添加了部分内容。
