面向大图的可达性查询算法研究

作     者：张海燕 

作者单位：燕山大学 

学位级别：硕士

导师姓名：周军锋

授予年度：2018年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

主      题：可达性查询 2-hop标签索引 妨碍点 

摘      要：可达性查询用于回答在有向图中从给定源点到终点是否存在一条路径。可达性查询处理是图数据处理中的基础操作之一,广泛应用于交通网络、社交网络、模式识别及生物信息网等图数据,支持复杂的数据分析,其查询处理的效率决定了众多图数据分析操作的效率,是研究者关注的热点问题之一。本文重点研究如何高效处理可达性查询,具体研究内容如下。首先,针对已有2-hop索引回答不可达查询效率低的问题,提出一种高效的可达性查询处理方法(Obstacle Labels,OL)。OL基于妨碍点的概念构建针对妨碍点的2-hop标签。和已有索引方法构建所有顶点的2-hop标签相比,本文提出的基于妨碍点的索引构建方法减少了2-hop标签所占用的空间,可以快速回答妨碍点正反传递闭包范围内顶点之间的可达性。在删除妨碍点的基础上,提出基于互逆的拓扑标签,用于回答妨碍点标签不能处理的查询。其次,针对OL在回答不可达查询时效率较低的问题,提出优化的方法OL+,用于同时高效回答可达和不可达查询。OL+在回答不可达查询时的高效性体现在所提出的既互逆又互补的拓扑标签,因而可以首先通过拓扑标签在常量时间里回答大部分可达和不可达查询。对剩余少量无法通过拓扑标签回答的查询,OL+采用基于妨碍点的2-hop标签进行处理。最后,基于33个真实的数据集进行实验测试,从索引构建时间、索引规模大小、可达性查询时间三个角度对实验结果进行分析,实验结果验证了本文方法查询的高效性。