计算机工程

• 先进计算与数据处理 • 上一篇    下一篇

面向大规模图数据的分布式可达性索引与查询策略

夏秀峰  a,b,张刘畅  b,刘向宇  a,b   

  1. (沈阳航空航天大学 a.辽宁省通用航空重点实验室;b.计算机学院,沈阳 110136)
  • 收稿日期:2017-01-22 出版日期:2018-03-15 发布日期:2018-03-15
  • 作者简介:夏秀峰(1964—),男,教授、博士,主研方向为数据库理论与技术;张刘畅(通信作者),硕士研究生;刘向宇,讲师、博士。
  • 基金项目:
    国家自然科学基金(61502316)。

Distributed Accessibility Index and Query Strategy for Large-scale Graph Data

XIA Xiufeng  a,b,ZHANG Liuchang  b,LIU Xiangyu  a,b   

  1. (a.Liaoning Province Key Laboratory of General Aviation; b.School of Computer,Shenyang Aerospace University,Shenyang 110136,China)
  • Received:2017-01-22 Online:2018-03-15 Published:2018-03-15

摘要: 针对构建大规模图数据可达性索引时的构建时间长、存储代价高和响应时间长等问题,提出一种分布式可达性索引与查询策略(DRIQ)。在不破坏原图中节点可达性的前提下,将大规模图划分成若干小规模子图,并对每个子图分布式并行地创建可达性索引,从而提高可达性索引创建效率。给出保持图划分后各子图内节点间以及子图间节点可达性的方法,从而保证基于DRIQ进行可达性查询的正确性。实验结果表明,与传统可达性查询方法相比,该策略具有高效性和可扩展性。

关键词: 大规模图数据, 图划分, 分布式, 可达性索引, 可达性查询

Abstract: Aiming at the problem of long construction time,high storage cost and long response time of reachability index of large graph,a Distributed Reachability Index and Query (DRIQ) strategy is proposed in this paper.Large graph is partitioned into several small subgraphs without destroying the reachability of the nodes.And reachability indexes are created for each subgraph distributed and parallel to improve the efficiency of index creating.Some methods are designed to keep the reachability of the nodes in the subgraphs and the reachability of the nodes between the subgraphs in DRIQ,which can ensure the correctness of the reachability query based on DRIQ.Experimental results show that the strategy is highly efficient and scalable,compared with the traditional reachability query method.

Key words: large-scale graph data, graph partition, distributed, accessibility index, accessibility query

中图分类号: