[1]陈伟,楼志斌,杨清章.一种基于悬挂顶点关联索引的最短路径查询算法[J].燕山大学学报,2018,42(3):265-271.[doi:10.3969/j.issn.1007-791X.2018.03.012]
 CHEN Wei,LOU Zhibin,YANG Qingzhang.A shortest path query algorithm based on related index of pendant vertex[J].Journal of YanShan University,2018,42(3):265-271.[doi:10.3969/j.issn.1007-791X.2018.03.012]
点击复制

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

《燕山大学学报》[ISSN:1007-791X/CN:13-1219/N]

卷:
42
期数:
2018年第3期
页码:
265-271
栏目:
信息与计算机技术
出版日期:
2018-05-31

文章信息/Info

Title:
A shortest path query algorithm based on related index of pendant vertex
文章编号:
1007-791X(2018)03-0265-07
作者:
 陈伟1楼志斌2*杨清章3
1.河北环境工程学院 信息工程系,河北 秦皇岛 066102;2.上海科学院,上海 201203;3.燕山大学 信息科学与工程学院,河北 秦皇岛 066004
Author(s):
 CHEN Wei1LOU Zhibin2YANG Qingzhang3
 1.Department of Information Engineering,Hebei University of Environmental Engineering,Qinhuangdao,Hebei 066102,China; 2.Shanhai Academy of Science & Technology,Shanghai 201203,China;
3.School of Information Science and Engineering,Yanshan University,Qinhuangdao,Hebei 066004,China
关键词:
最短路径查询悬挂顶点顶点关联索引2-hop标签索引
Keywords:
graphshortest path querypendant vertexvertex-related index2-hop label index
分类号:
TP392
DOI:
10.3969/j.issn.1007-791X.2018.03.012
文献标志码:
A
摘要:
最短路径查询是图数据查询中的热点问题。针对现有的“索引+查询”方法存在的查询效率低下且扩展性差等问题,本文提出了悬挂顶点关联索引策略,即先对度为1的顶点构建顶点关联索引,再对其他顶点构建2-hop标签索引,并依此提出了相应的最短路径查询算法。本文提出的索引策略降低了索引规模,减少了构建索引时间,使得最短路径查询算法的效率和扩展性得到了改善。最后,通过对11个真实的数据集进行实验,从索引构建时间、索引规模大小、查询时间等方面验证了本文方法的高效性。
Abstract:
The shortest path query is one of hottest issues in the field of graph data query.The existing methods usually use "index + query" strategy to deal with the shortest path query and have the problems of low query efficiency and poor scalability.Therefore,an related index strategy based on the pendant vertex is proposed,which is to construct the related index for the vertex of one degree and then construct 2-hop label index for the other vertices.On this basis,the corresponding shortest path query algorithm is proposed.The proposed index strategy can reduce the size of index and the index construction time,and make the efficiency and expansibility of the shortest path query algorithm improved.Finally,the experiment on the 11 real data sets verify the high efficiency of the proposed method compared with the existing methods from the following aspects,such as the time of the index construction,the index scale,and the query response time.

备注/Memo

备注/Memo:
收稿日期:2017-12-31      责任编辑:孙峰
基金项目:国家自然科学基金资助项目(61472339,61572421);河北省高等学校科学技术研究重点项目(ZD2018048)
作者简介:陈伟(1980-),女,河北秦皇岛人,博士研究生,副教授,主要研究方向为图数据查询处理;*通信作者:楼志斌(1966-),男,浙江义乌人,硕士,高级工程师,主要研究方向为大数据处理,Email:zblou@163.com
更新日期/Last Update: 2018-07-16