HybriG:一种高效处理大量重边的属性图存储架构

• 作者: 任鑫琦 冯是聪 孟嘉 崔斌 邵蓥侠 黄权隆 黄艳香
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 属性图 重边 图数据库 Titan HBase
• 年，卷（期）: 2018,（8）
• 所属期刊栏目: 数据科学与工程
• 页码范围: 1766-1779
• 页数: 14页
• 分类号: TP18
• 字数: 12979字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2018.01766

摘要

在图中,起点和终点都相同的两条边称为重边.属性图是一种带标志和重边的有向图,图中的点和边可以拥有任意数目的属性值.属性图由于其丰富的表达能力而广泛应用于实际建模中.实际应用中一般用图数据库解决属性图的存储需求.相比于传统的关系型数据库,图数据库在做多跳邻域查询、路径查询等与图结构相关的查询时,具有更优异的性能.Titan是产业界日渐关注的一个开源的分布式图数据库,Titan的数据以邻接表的方式组织,每个点的邻接表存储了相邻的所有边,这使得与邻接点集相关的查询都需要遍历整个邻接表.当图中含有大量重边时,邻接表规模巨大,这种数据组织方式导致邻域查询性能严重受损.邻域查询是大部分图查询的基础,如多跳邻域查询、路径查询、局部聚集系数查询(计算)等,这些查询往往由嵌套的邻域查询实现,随着邻域深度的增加,这种性能受损将被急剧放大.文中提出了一种基于Titan和列式存储数据库HBase的复合架构设计——HybriG,基于Titan和HBase建立存储层,用Titan来存储图的结构信息和点集的属性信息,HBase存储边集的所有属性信息.在HybriG中邻接表保持了项数和数据量上的精简,从而能克服上述图数据库的缺点.相比于传统图数据库Titan,HybriG在邻域点集相关查询以及边集数据批量导入上的性能提升一个量级以上.文中介绍了HybriG基于Titan和HBase的存储设计,并描述了在此存储设计基础上,如何高效地实现图查询以及图数据的插入操作.此外,文中还提出了图数据的高效导入方案,并保证导入过程中Titan与HBase存储数据的一致性.最后通过实验验证了HybriG在处理大量重边时的优异性能.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	崔斌	北京大学信息科学技术学院高可信软件技术重点实验室	53	357	10.0	17.0
2	邵蓥侠	北京大学信息科学技术学院高可信软件技术重点实验室	3	5	1.0	2.0
3	黄权隆	北京大学信息科学技术学院高可信软件技术重点实验室	1	1	1.0	1.0
4	黄艳香	北京大学信息科学技术学院高可信软件技术重点实验室	1	1	1.0	1.0
5	孟嘉		1	1	1.0	1.0
6	任鑫琦		1	1	1.0	1.0
7	冯是聪		2	3	1.0	1.0