-
题名基于顶点关联索引的最短路径查询算法研究
被引量:1
- 1
-
-
作者
余靖
杨清章
-
机构
燕山大学信息科学与工程学院
河北省计算机虚拟技术与系统集成重点实验室
河北省软件工程重点实验室
-
出处
《高技术通讯》
北大核心
2017年第11期899-906,共8页
-
基金
国家自然科学基金(61572421)资助项目
-
文摘
研究了图查询中的最短路径查询问题,针对现有的查询算法存在构建索引时间长和索引规模庞大所导致的低效性和扩展性问题,在索引构建方面提出了顶点关联索引策略。对度数为1的顶点构建顶点关联索引,对其他顶点构建2-hop标签索引,通过减少冗余数据存储和图的遍历次数,降低索引规模以减少构建索引时间。基于所提出的查询策略,给出了基于顶点关联关系和2-hop标签的最短路径查询算法。
-
关键词
图模型
最短路径查询
顶点关联索引
2-hop标签索引
-
Keywords
graphical model, shortest path query, vertex-related index, 2-hop label index
-
分类号
TP311.13
[自动化与计算机技术—计算机软件与理论]
-
-
题名一种基于悬挂顶点关联索引的最短路径查询算法
被引量:7
- 2
-
-
作者
陈伟
楼志斌
杨清章
-
机构
河北环境工程学院信息工程系
上海科学院
燕山大学信息科学与工程学院
-
出处
《燕山大学学报》
CAS
北大核心
2018年第3期265-271,共7页
-
基金
国家自然科学基金资助项目(61472339
61572421)
河北省高等学校科学技术研究重点项目(ZD2018048)
-
文摘
最短路径查询是图数据查询中的热点问题。针对现有的"索引+查询"方法存在的查询效率低下且扩展性差等问题,本文提出了悬挂顶点关联索引策略,即先对度为1的顶点构建顶点关联索引,再对其他顶点构建2-hop标签索引,并依此提出了相应的最短路径查询算法。本文提出的索引策略降低了索引规模,减少了构建索引时间,使得最短路径查询算法的效率和扩展性得到了改善。最后,通过对11个真实的数据集进行实验,从索引构建时间、索引规模大小、查询时间等方面验证了本文方法的高效性。
-
关键词
图
最短路径查询
悬挂顶点
顶点关联索引
2-hop标签索引
-
Keywords
graph
shortest path query
pendant vertex
vertex-related index
2-hop label index
-
分类号
TP392
[自动化与计算机技术—计算机应用技术]
-