图数据模型是数据管理领域的三大结构化数据模型之一。图数据模型表达能力强,操作复杂性高。大规模图结构计算已经成为网络、社交、金融、交通的一个基础性数学交叉计算机学科研究, 例如:滴滴出行的行为分析、阿里、京东等电商交易数据处理、微信、微博等社交网络关系模型提取等。目前,Google、Facebook开发了分布式大图处理框架,并成功应用于大规模网页分析、社交网络发现等实际场景。

大数据处理中, 包括现在兴起的知识图谱,异构图都是一种普遍存在的数据模型,可以用于抽象表示真实世界中丰富的语义关联关系。异构图处理过程中的一个重要步骤是从异构图中抽取同构图,亦称之为齐次图。提取问题的关键挑战是如何快速枚举找出符合规则的所有路径和聚合相应匹配的路径数值计算。

云计算重点实验室发表的《Fast Parallel Path Concatenation for Graph Extraction》论文针对上述需求,提出一种快速高效的基于关联路径分步级联的齐次图的并行提取算法: 为了解决之前的两个挑战,提出了一个并行图抽取框架,使用顶点为中心的模型来枚举路径且并行计算聚合函数。该框架将路线查询模式分解为路径级联方案,确定连接路径的顺序,采用分治法(divide-and-conquer manner)逐步计算出最终完整路径。算法模型中引入了一个成本模型,分别对比讨论了三种选择策略,其中最好的方案可以达到O(log(L))级别的计算复杂度,其中L是模式的长度。此外,为了提高聚合函数的性能,算法将聚合函数分为分布聚合、代数聚集和整体聚集三类。由于分布、代数聚合进行独立的局部性计算,并行计算部分聚合值从而可以加快整体聚合速度。

文章已经优先在IEEE Xplore在线发表,TKDE全称为“IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING”,是CCF推荐的A类期刊之一,排名JCR一区,2016年的影响因子为3.438,文章的通讯作者是雷凯老师。