大图数据体系结构的理论、系统与应用
从人类进入信息时代以来，图论的应用非常广泛，比如用图论来确定最优运输路线、预测疾病爆发路径、确立科技文献的引用关系、分析生物信息网络等。
■袁野
自1738年大数学家欧拉解决柯尼斯堡问题以来，图论已经有近300年的发展历史。从人类进入信息时代以来，图论起到了不可替代的作用，因为其应用非常广泛，比如用图论来确定最优运输路线、预测疾病暴发路径、确立科技文献的引用关系、分析生物信息网络等。简单地说，图是表示对象与对象之间关系的方法，一个图由若干顶点和连接它们的边组成。在大数据时代，图又被称为“大图数据”。
大图数据特点
大图数据有很多新型的应用，以下是三个典型的例子。
一是人脑网络分析。脑网络是一个复杂的大图，人脑中含有上百亿个神经元（即大图中的顶点），它们之间的连接（即大图中的边）规模可达数万亿。人脑网络具有“局部特征多样性”这一特点，即不同区域具有不同的统计特性，如Brodmann分区（编者注：一个根据细胞结构将大脑皮层划分为一系列解剖区域的系统）将大脑分为52个分区，每个分区都有不同的细胞纤维分布。
二是知识图谱分析。知识图谱是结构化的语义知识库，以符号形式描述物理世界中的概念及其相互关系，目前谷歌知识图谱规模达到数十亿个顶点。知识图谱中实体描述包含文本、图片等复杂数据，如医学知识图谱中的病例包含不同的病情描述文本及X线检查图片等。知识图谱的数据特点是“关联数据复杂性”，其顶点、边、子图的关联数据非常复杂，顶点和边上的属性与标签值有多样性，且在匹配这些属性和标签的子图之间，统计特征差别巨大。
三是物联网络分析。物联网络是任何物品与物品之间进行信息交换和通信的网络，现在最大规模达到百亿，并且还在飞速扩大，每天都有新的物联设备加入到物联网中，同时也有大量设备衰败淘汰。这将导致网络拓扑结构的深度改变，使得物联网络具有“拓扑结构时变性”，即拓扑结构随时间变化而快速变化，如传感网络中局部区域突发信号中断造成大面积网络瘫痪。
从上述三个应用可以看出，大图数据不但具有大数据的4V（大量、多样、高速、价值）特点，还具有局部特征多样性、关联数据复杂性以及拓扑结构时变性等特点，这导致大图数据应用的自适应存储难、查询结果失效快以及计算复杂度高，为其研究带来了巨大的挑战。
大图数据计算理论与模型
为了更好地支持大图数据应用，适应其特点，我们提出了大图数据计算理论，其思想是用图树分解的“树宽”作为参数，结合参数计算理论和大数据计算理论，给出不同参数粒度下“难解问题”和“高效问题”。
现有的大图计算模型有很多，其中代表性的包括MapReduce和Pregel。MapReduce不是专为大图处理而设计的，其每次迭代的中间结果都需要被保存作为下次迭代的输入，每次迭代都传输整个图数据，网络开销大。而Pregel是专为大图处理而设计的，运行图的算法更加自然，但是Pregel不传递图结构，只在节点间传递消息，因此节点间消息迭代次数多，这使得网络开销大。我们用大图数计算理论分析了上述两个计算模型，从理论上给出Pregel优于MapReduce的本质原因，并证明有比Pregel更适合大图数据的计算模型。
由于现有方法的局限性，我们提出了基于树分解的大图计算模型。该模型的计算模式如下：
首先输入一个大图G，基于树分解的大图计算模型采用启发式算法得到G的树分解T，用w表示T的树宽；然后通过T得到一个树宽为3w+2的二叉平衡树分解T’；接着将T’映射到实际的物理网络中得到T’’；最后基于T’’采用并行动态规划编程技术解决G上的经典问题，如聚类、PageRank、图模式挖掘、机器学习等。理论和实验证明了我们提出的计算模型可以使对大图数据算法的“统一化”、问题空间不同粒度分解、计算密集的“集中化”以及通信密集的“分散化”，以此避免MapReduce和Pregel中的多次迭代问题。
大图数据库机
基于树分解的计算模型可以从逻辑上加速大图计算的速度，但是逻辑的加速存在瓶颈。为了更好地解决大图数据的计算问题，我们基于新型硬件提出了图数据库机的概念。
图数据库机是指图数据管理软件和标准硬件一体定制的服务器，集图数据存储、图数据处理和图数据传输于一体。其目标是采用分布式并行架构显著增加图数据处理能力，来线性或准线性扩展图数据存储能力、处理能力以及传输能力。图数据库机要基于树分解并行体系结构和基于图代数的查询处理制定设计方案。给定一个查询，首先在解析引擎中通过图代数对查询进行逻辑处理以及优化，然后将查询计划发送到内联传输网络中，通过树分解将查询内容分配给不同计算节点和存储节点中，在计算节点和存储节点中通过图代数对数据进行物理处理与优化，最后合并结果并返回。图数据库机结合了新型硬件的优势，在内联传输网络应使用Omni-Path、InfiniBand等来提升传输并降低网络随机读写，在计算节点应采用FPGA、GPU等来提升数据处理能力，在存储节点可采用SSD、闪存等来提升数据存储能力，并使用大Cache以降低磁盘的随机读写。
健康医疗知识图谱
健康医疗大数据涵盖人的全生命周期，既包括个人健康，又涉及医药服务、疾病防控、健康保障和食品安全和养生保健等多方面数据的汇聚和聚合，因此健康医疗数据规模宏大，很多数据都以TB为单位。由于健康医疗数据的多样性，如音频、图像、影像序列、文本报告等，因此医疗健康数据种类繁多。并且，由于很多疾病暴发迅速，如流行疾病，因此医疗健康数据速度变化快。综上所述，医疗健康数据具有典型的大数据特征。
通过与东软集团的合作，我们可触及到多家医院在5年内医疗健康领域产生的海量、异构、分布式数据。我们通过数据整合，构建健康医疗知识图谱，通过大图数据库机实现对医疗健康大数据的管理与分析。
（作者系东北大学计算机学院教授，此文据其在2019计算机体系结构国重首届前沿高峰论坛上的发言整理）
《中国科学报》 (2019-01-24 第7版 信息技术)
