一种基于悬挂顶点关联索引的最短路径查询算法

• 作者: 杨清章 楼志斌 陈伟
• 来源期刊: 燕山大学学报
• 学科: 工学
• 关键词: 图 最短路径查询 悬挂顶点 顶点关联索引 2-hop标签索引
• 年，卷（期）: 2018,（3）
• 所属期刊栏目: 信息与计算机技术
• 页码范围: 265-271
• 页数: 7页
• 分类号: TP392
• 字数: 6054字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-791X.2018.03.012

摘要

最短路径查询是图数据查询中的热点问题.针对现有的"索引+查询"方法存在的查询效率低下且扩展性差等问题,本文提出了悬挂顶点关联索引策略,即先对度为1的顶点构建顶点关联索引,再对其他顶点构建2-hop标签索引,并依此提出了相应的最短路径查询算法.本文提出的索引策略降低了索引规模,减少了构建索引时间,使得最短路径查询算法的效率和扩展性得到了改善.最后,通过对11个真实的数据集进行实验,从索引构建时间、索引规模大小、查询时间等方面验证了本文方法的高效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	楼志斌		21	97	6.0	8.0
2	陈伟	河北环境工程学院信息工程系	8	18	3.0	4.0
3	杨清章	燕山大学信息科学与工程学院	2	7	1.0	2.0