HybriG:一种高效处理大量重边的属性图存储架构
在图中,起点和终点都相同的两条边称为重边.属性图是一种带标志和重边的有向图,图中的点和边可以拥有任意数目的属性值.属性图由于其丰富的表达能力而广泛应用于实际建模中.实际应用中一般用图数据库解决属性图的存储需求.相比于传统的关系型数据库,图数据库在做多跳邻域查询、路径查询等与图结构相关的查询时,具有更优异的性能.Titan是产业界日渐关注的一个开源的分布式图数据库,Titan的数据以邻接表的方式组织,每个点的邻接表存储了相邻的所有边,这使得与邻接点集相关的查询都需要遍历整个邻接表.当图中含有大量重边时,邻接表规模巨大,这种数据组织方式导致邻域查询性能严重受损.邻域查询是大部分图查询的基础,如多跳邻域查询、路径查询、局部聚集系数查询(计算)等,这些查询往往由嵌套的邻域查询实现,随着邻域深度的增加,这种性能受损将被急剧放大.文中提出了一种基于Titan和列式存储数据库HBase的复合架构设计——HybriG,基于Titan和HBase建立存储层,用Titan来存储图的结构信息和点集的属性信息,HBase存储边集的所有属性信息.在HybriG中邻接表保持了项数和数据量上的精简,从而能克服上述图数据库的缺点.相比于传统图数据库Titan,HybriG在邻域点集相关查询以及边集数据批量导入上的性能提升一个量级以上.文中介绍了HybriG基于Titan和HBase的存储设计,并描述了在此存储设计基础上,如何高效地实现图查询以及图数据的插入操作.此外,文中还提出了图数据的高效导入方案,并保证导入过程中Titan与HBase存储数据的一致性.最后通过实验验证了HybriG在处理大量重边时的优异性能.
属性图、重边、图数据库、Titan、HBase
41
TP18(自动化基础理论)
国家自然科学基金61572039;国家“九七三”重点基础研究发展规划项目基金2014CB340405;深圳政府研究项目JCYJ20151014093505032
2018-09-20（万方平台首次上网日期，不代表论文的发表时间）
共14页
1766-1779
