大图上的K跳可达性查询算法

摘要

k跳可达性查询是图可达性查询问题的一般形式，在社交网络和传感器网络领域有很重要的应用。随着图数据的规模不断扩大，大图中的可达性查询问题受到了越来越多的关注。传统的可达性查询算法不能有效地支持大图上的可达性查询，而一些具有扩展性的可达性查询算法由于索引中缺乏距离信息，在查询过程中不能有效地通过索引判断那些具有可达性但是不具有 k跳可达性的顶点对，因而应用于大图上的k跳可达性查询时，不能达到k跳可达性查询算法的及时性要求。
　　为了提高算法的扩展性，根据k跳可达性查询的特点，将具有扩展性的可达性查询索引与广度优先遍历得到的距离索引结合起来完成查询，从而减少在线搜索的搜索空间，提高了算法的查询效率。其中，系统的索引构造结合了FELINE索引、BFSI索引两种关键索引技术。主要研究内容包括，提出基于广度优先树的 BFSI索引的构建方法，通过生成广度优先树的区间索引来记录部分顶点的距离信息；针对现实图中存在的power-law分布，提出了一种新的广度优先树的构造方法BFSI-S，相比于基于根节点构建的广度优先树，可以有效提高索引算法的覆盖率。然后根据图的入度和出度的差异，提出了针对逆向图的BFSI-B索引，结合双向搜索的方法，进行双向剪枝，大大提高了剪枝的效率。
　　在大量具有不同特征的有向无环图中，对k跳可达性查询算法进行了详细的测试。测试结果表明，相比于传统的k跳可达性查询方法，在相同的硬件条件下，能够支持更大规模图的k跳可达性查询，索引大小和查询时间都优于最新的scalable k-reach方法。算法具有良好的扩展性和时间效率，能够适应大图上的k跳可达性查询的要求。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 研究背景及意义

1.2 国内外研究现状

1.3 本文主要研究内容

1.4 论文组织结构

2 图论及相关算法基础

2.1 图的相关概念

2.2 可达性基本概念

2.3 K跳可达性的相关算法

2.4 本章小结

3 基于索引集的k跳可达性算法

3.1 算法基础

3.2 FELINE索引的构建

3.3 基于广度优先树的索引BFSI

3.4 逆向图上的索引BFSI-B

3.5 高度数顶点的危机

3.6 查询算法设计

3.7 本章小结

4 实验结果与分析

4.1 测试指标与测试集

4.2 测试环境

4.3 测试结果

4.4 本章小结

5 总结和展望

5.1 总结

5.2 研究展望

致谢

参考文献

附录1 攻读学位期间参加的主要科研项目

附录2 攻读学位期间申请的国家发明专利