大图上的k步可达性查询算法研究

作     者：同正南 

作者单位：华东师范大学 

学位级别：硕士

导师姓名：卜天明

授予年度：2023年

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

主      题：k步可达性查询 标签索引 动态规划 倍增索引 动态索引 

摘      要：可达性查询已经应用于有向无环图网络中的多个地方,例如社交网络、XML文档结构、生物网络分析、代谢网络、引用网络、传感器网络、数据库术语关系等多个领域。可达性查询是指给定任意两点u和v,回答节点u是否可达节点v。而k步可达性查询是指对于任意两点回答节点u是否可在k步以内到达节点v。针对于现有k步可达性查询算法在大图上构建索引规模过大,创建的索引不能对任意k值具有一般适用性,且查询效率一般等问题。本文提出了一个新的k步可达性查询算法。本文的主要贡献如下:(1)提出在原有向无环图上构建最短路径森林,在最短路径树上构建自适应k值的倍增索引,在此基础上设计出基于倍增索引的k步可达性查询算法,并分析了查询算法的正确性和时间复杂性,成功将k步可达性问题扩展至大图。(2)针对高密度节点构建动态索引,提高了对于关注度较高的高密度查询点对的查询性能,在经典伸展树基础上扩展出基于双关键字伸展的动态索引表,并提出了针对动态索引的查找、更新算法。(3)最后在19个真实的数据集上和已有算法进行比较,验证了倍增索引在索引构造时间、索引大小、查询时间上的高效性,动态索引在应对高密度点对查询的高效性。