• 主题
高级搜索  >
历史搜索 清空历史
首页> 中文期刊> 《计算机学报》 >HybriG:一种高效处理大量重边的属性图存储架构

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

         
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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

著录项

  • 来源
    《计算机学报》 |2018年第8期|1766-1779|共14页
  • 作者

    黄权隆; 黄艳香; 邵蓥侠; 孟嘉; 任鑫琦; 崔斌; 冯是聪;

  • 作者单位

    北京大学信息科学技术学院高可信软件技术重点实验室 北京 100871;

    北京大学信息科学技术学院高可信软件技术重点实验室 北京 100871;

    北京大学信息科学技术学院高可信软件技术重点实验室 北京 100871;

    北京明略软件系统有限公司 北京 102218;

    北京明略软件系统有限公司 北京 102218;

    北京大学信息科学技术学院高可信软件技术重点实验室 北京 100871;

    北京明略软件系统有限公司 北京 102218;

  • 原文格式 PDF
  • 正文语种 chi
  • 中图分类 人工智能理论;
  • 关键词

    属性图; 重边; 图数据库; Titan; HBase;

相似文献

  • 中文文献
  • 外文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号