近年来,数十亿顶点规模的大图数据大量出现,不断地对数据管理技术提出了新的要求。万维网目前已经包含了超过500亿个网页以及数量达万亿级别的统一资源定位符,社交网络Facebook存储的好友网络包含了超过8亿个节点和1000亿条边。语义网领域的链接数据规模正迅速呈指数方式提升,目前已包含了310亿个资源描述框架(Resource Description Framework,RDF)三元组以及超过5亿个RDF链接。在生物信息学领域,全基因组序列数据分析的关键环节之一是序列拼接。当前的面向短序列拼接的主流方法是基于德布鲁因图(Brujin graph)的拼接方法。而人类基因组上的德布鲁因图在最坏情况下具有420个节点。

图存储技术主要研究图数据在磁盘上存储以及分布式环境下的存储布局形式、划分方法、复制方法等一系列方法,图存储技术是图数据管理的基石。图的存储方式直接决定了图数据的访问方式、图查询方式与挖掘的效率。

(一)大图存储的基本框架

大图存储的基本框架是分布式存储框架,其原因如下。

1.大图数据规模大

10亿顶点规模的大图的每个顶点或者边上存储的附加信息,其规模在TB级别,甚至达到PB级。

2.利用了基于分布式内存的计算框架

为了实现对整个图进行随机访问而不是顺序访问,图计算必须基于内存展开。由于当前内存规模在GB(109字节)级别,通过分布式存储就可以直接装入内存,从而降低每台机器上的图的规模,避免频繁进行磁盘交互。

(二)图划分技术

大图的分布式存储的核心技术是图划分技术。为了将图部署到分布式系统中,需要将图分为若干部分,而后将每一部分分别存入某一机器。具体而言,图划分是一类问题的集合,这类问题需要将顶点集合划分为若干单元,这些单元的并集构成总体的顶点集,任意两个单元相交为空。在考虑通过顶点复制减少通信的策略中,需要放松单元不相交的约束。通常考虑下述集中因素。

图计算是通过边对顶点进行访问与遍历,跨越机器的边数决定图系统的网络通信开销。通常将两个端点存储在不同机器上的边称作交叉边。对于非本地数据的访问而导致的网络通信代价非常高。访问本地内存数据的时间通常以纳秒计算,而网络通信时间则通常以毫秒计算,两者时间相差巨大。所以图划分的方式直接决定了交叉边的数量,从而决定了基于该划分方式的图计算所需的通信代价。通常,我们期望交叉边数量最小化,进而降低通信代价。图划分主要考虑负载均衡与存储冗余问题。

1.负载均衡

避免网络通信代价的极端方法是将完整的图信息仅存储于一台机器上。显然,这一方式很可能超出单台机器的存储上限,同时这一方法也没有并行计算能力。期望图划分的各个部分具有相近的规模,从而避免负载失衡的情况。负载均衡是相对于机器存储容量和计算能力而言的。在复杂的实际应用中,可以构建复杂的度量模型用以刻画兼顾机器存储容量和计算能力的负载均衡模型。

2.存储冗余(www.daowen.com)

避免网络通信代价升高的另一极端方法是将图的信息在每台机器上复制一份。但这种方法也容易超出单台机器的存储能力,同时导致大量冗余。对于k台机器的分布式系统,这种方法导致k-1份存储冗余。为了降低冗余,可以选择特定顶点及其邻接信息进行复制。通常选择度数较大的顶点进行复制,从而在降低通信代价的同时,避免较大冗余。此外,复制顶点个数和位置的选择等都对最终结果有着直接影响。另外,多个副本之间的一致性也是重要的问题,通常需要额外的计算代价保持多份副本与主本的完全一致性。

(三)大图数据的查询

如果用图表示社交网络,用户可以看作图的顶点,用户之间的关系(如朋友关系等)可以看作图的边。与社交网络相类似,Web网络中的网页可以看作图的顶点,网页之间的链接关系可以看作图的边。图在社交网络中有着重要的应用。

计算机查询方式经历了文件系统查询、数据库系统查询、Web网络查询、社会网络查询的发展历程,如图4-4所示。

图4-4　查询的演变过程

1.文件系统

从20世纪60年代开始,计算机开始装配了具有现代意义的操作系统,而文件系统是操作系统提供的一种存储和组织计算机文件的方法。它提供简单的查询功能,用户可以搜索文件。

2.数据库系统

20世纪60年代中期,数据库系统开始应用。20世纪70年代,关系数据模型成为数据库管理系统的主流系统。70年代后期出现的结构化查询语言SQL,极大地提高了数据查询的灵活性。用户可以通过SQL语言来进行各种复杂的查询。

3.Web网络

从20世纪90年代开始,随着万维网的兴起,Web搜索引擎被广泛应用。它们通过提供关键词搜索的功能,使得几乎所有的用户都可以方便地搜索万维网数据。

4.社会网络

随着Web 2.0的出现和社会计算的兴起,社交网络系统开始大量应用,如Facebook、LinkedIn、人人网等。图查询技术是适合社会计算的搜索方式。社会计算一般需要考虑社会的结构、组织和活动等社会因素。所有的社会活动构成了社会网络,本质上这是图的一种表现形式,所以图搜索技术的研究成为关键技术。