分布式环境下海量图数据的可达性查询研究

发布时间：2017-12-18 15:42

  本文关键词：分布式环境下海量图数据的可达性查询研究

  更多相关文章： 分布式计算 可达性查询 图划分 可达性索引

【摘要】：图数据信息的应用极其广泛,存在于科学技术的各个领域,因此经常会遇到图数据信息中有关可达性查询的计算问题。随着数据量的急剧增长,传统的可达性计算方法已经无法满足大型图数据上的计算,这使得如何在大型图数据上进行可达性查询成为了一个亟待解决的问题。图数据的可达性查询与其计算模型及处理算法密切相关。传统的可达性计算方法存在本地局限、处理数据量不足及扩展性差等缺点,其改良算法在百万级别顶点的图数据上也有限制,只适用于在单机环境中进行计算。针对海量图数据的可达性问题,设计了在分布式环境下海量图数据的可达性计算框架,提供了一种可以对千万级顶点和亿级边的图数据进行可达性查询的方法。针对于传统的可达性方法无法有效地处理分布式海量图数据的问题,设计了基于分布式文件系统的海量图数据的可达性计算框架。计算框架中对图进行了预处理,并设计了在分布式环境下针对可达性查询问题的均衡拓扑划分策略,经过一次划分使得子图内部拥有较好的内聚性;设计了分布式跨子图索引,在子图上找出骨干顶点和外部联系顶点建立索引,用于有效地在划分后的子图内部和子图之间进行并行的可达性查询计算。通过图划分以及可达性连接测试表明,利用海量图数据的可达性计算框架,可以有效地对分布式下千万级顶点和亿级边的图数据进行可达性查询。
【学位授予单位】：华中科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5;TP391.3

【参考文献】

中国期刊全文数据库 前1条

1 郑丽丽;;图划分算法综述[J];科技信息;2014年04期

，

本文编号：1304730