A novel shortest path query algorithm
A novel shortest path query algorithm
复制标题
一种新颖的最短路径查询算法
DOI：
10.1007/s10586-018-2554-8
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
ziyang chen
中科院分区：
文献类型：
--
作者：
wei chen;ziyang chen
最短路径查询是图论研究的热点问题之一。针对现有方法中索引构建时间长、索引规模大导致的查询效率低、可扩展性差的问题，提出了一种基于单分支路径顶点的关联索引策略，即对单个分支路径顶点构建关联索引，对其他顶点构建2-hoplabel索引，通过减少冗余数据存储和图的遍历次数来减少索引的大小和构建时间。然后提出了相应的基于单分支路径顶点关联索引的最短路径查询算法。然后，将核顶点的概念引入到2-hoplabel索引的构造中，进一步减少了图的遍历次数，提高了索引构造效率。并将其应用于大型图的最短路径查询算法。最后，通过在12个真实数据集上的测试，从索引构建时间、索引大小和最短路径查询时间等方面与现有方法进行了比较，验证了本文方法的高效性。
The shortest path query is one of the hot issues in graph research. In view of the low query efficiency and poor scalability caused by the long time of the construction of index and the large scale of index in the existing methods, we propose an associated index strategy based on the single branch path vertices, which is to construct the associated index for the vertex of single branch path vertices and construct the 2-hoplabel index for the other vertices in order to reduce the size and construction time of index by reducing the number of redundant data storage and graph traversal. Then we propose the corresponding shortest path query algorithm based on the single branch path vertices associated index. And then, we introduce the concept of core vertex for the construction of the 2-hoplabel index, which can further reduce the number of graph traversal and improve the efficiency of index construction. And we apply it to the shortest path query algorithm for the large graphs. Finally, according to test on the 12 real datasets, we verify the high efficiency of the method proposed in this paper compared with the existing methods from the following aspects, such as the index construction time, the index size and the shortest path query time.
登录
查看更多内容
DOI：
--
发表时间：
1967
期刊：
--
影响因子：
--
作者：
J. E. Falk;R Fletcher;M. J. D. Powell;Peter E Hart;Nils J Nilsson;Bertram Raphael
通讯作者：
J. E. Falk;R Fletcher;M. J. D. Powell;Peter E Hart;Nils J Nilsson;Bertram Raphael
DOI：
10.1109/tkde.2016.2593464
发表时间：
2016-10
期刊：
2017 IEEE 33rd International Conference on Data Engineering (ICDE)
影响因子：
--
作者：
Yu Gu;Guanli Liu;Jianzhong Qi;Hongfei Xu;Ge Yu;Rui Zhang
通讯作者：
Yu Gu;Guanli Liu;Jianzhong Qi;Hongfei Xu;Ge Yu;Rui Zhang
DOI：
--
发表时间：
2013
期刊：
Journal of Yanshan University
影响因子：
--
作者：
Deng Cheng-y
通讯作者：
Deng Cheng-y
DOI：
10.14778/3015274.3015277
发表时间：
2016-10
期刊：
Proc. VLDB Endow.
影响因子：
--
作者：
Sibo Wang;Xiaokui Xiao;Y. Yang;Wenqing Lin
通讯作者：
Sibo Wang;Xiaokui Xiao;Y. Yang;Wenqing Lin
DOI：
10.14778/2536206.2536217
发表时间：
2013-08
期刊：
Proc. VLDB Endow.
影响因子：
--
作者：
Miao Qiao;Lu Qin;Hong Cheng;J. Yu;Wentao Tian
通讯作者：
Miao Qiao;Lu Qin;Hong Cheng;J. Yu;Wentao Tian