面向亿级图的高效索引和查询系统

发布时间：2022-02-21 06:01

　　图常用的查询算法有可达性、最短路径距离和最宽路径查询等,传统查询算法有两种:一种是求解完整传递闭包,即预计算出所有的结果,那么查询效率为（1）;另一种则是使用修改的Dijkstra算法或其他算法直接在原图上进行搜索,空间开销为（1）。而近年来图规模快速增长,其节点和边的总数可以达到亿级规模。针对如此大规模的图,前者查询效率虽高,但是空间开销使其难以扩展;后者虽然空间开销（1）很低,但直接在原图搜索的算法往往因其过高的时间复杂度,无法满足一些实时性要求很高的应用。因此在大规模图中,如何进行快速高效地查询是极具挑战意义的。面向亿级图的高效索引和查询系统是为了解决传统算法在大规模图处理中,查询效率低或者空间复杂度过高的问题。该系统基于2-hop label索引结构,采用空间换时间的思想,在查询效率和空间复杂度之间获得平衡。并提出了一个基于剪枝思想的最宽路径索引算法,该算法在处理大规模图时,能使索引规模显著降低。算法为每个节点依次执行剪枝的Dijkstra算法,并产生索引标签。其能减少索引时间和索引大小的核心关键是引入一个剪枝的操作。除此之外,本系统还集成了能支持亿级规模图的最短路径、可达性查... 

【文章来源】：华中科技大学湖北省211工程院校985工程院校教育部直属院校

【文章页数】：60 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
1 绪论
    1.1 项目研究背景及意义
    1.2 国内外研究现状
    1.3 本文主要工作
    1.4 论文组织结构
2 最宽路径的索引算法设计
    2.1 相关定义
    2.2 问题与挑战
    2.3 算法设计
    2.4 节点排序策略
    2.5 算法正确性证明
    2.6 查询效率分析
    2.7 本章小结
3 系统设计与实现
    3.1 系统架构
    3.2 索引构建
    3.3 查询引擎
    3.4 本章小结
4 系统测试与性能分析
    4.1 系统实现与实验环境
    4.2 测试数据集
    4.3 测试方法
    4.4 最宽路径算法性能测试
    4.5 集成模块测试
    4.6 本章小结
5 总结及展望
致谢
参考文献
附录1 攻读硕士学位期间申请的计算机软件著作权
附录2 攻读硕士学位期间参与的项目


【参考文献】：
期刊论文
[1]一种基于悬挂顶点关联索引的最短路径查询算法[J]. 陈伟,楼志斌,杨清章.  燕山大学学报. 2018(03)
[2]基于顶点关联索引的最短路径查询算法研究[J]. 余靖,杨清章.  高技术通讯. 2017(Z2)
[3]基于双区间标签的大规模图可达性索引[J]. 李婷婷,古天龙.  桂林电子科技大学学报. 2017(04)
[4]基于QoS的服务个性化选择路由[J]. 刘岩,刘建明,任莉莉.  计算机工程与设计. 2016(04)
[5]寻找最大带宽的独立路径对算法[J]. 谢政,张晓明,陈挚.  国防科技大学学报. 2012(05)
[6]关于实际构造最大带宽路径算法的研究[J]. 陈建二,王伟平,张祖平.  福州大学学报(自然科学版). 2001(04)



本文编号：3636645