图划分对Arc-flags算法的影响
作者简介:刘惠民(1991-),男,硕士生,主要从事高性能计算、大数据处理研究。E-mail: huimin@mail.ustc.edu.cn
收稿日期: 2016-07-21
要求修回日期: 2016-09-30
网络出版日期: 2016-11-20
基金资助
国家自然科学基金青年科学基金项目(61303047)
The Influence of Graph Partitioning on Arc-flags Algorithm
Received date: 2016-07-21
Request revised date: 2016-09-30
Online published: 2016-11-20
Copyright
最短路径计算作为导航的常用算法在移动互联网中扮演了重要角色,由于路网规模的增大和终端的不停移动,传统的串行最短路径算法已经无法满足实时性要求,因此预处理技术得到了广泛使用。Arc-flags是一个经典的基于预处理技术的最短路径算法,可以提供高效的在线最短路径查询服务。现有Arc-flags算法的研究主要集中在提升预处理时空效率和比较不同路网划分方式的优劣上,尚未见图划分对Arc-flags算法影响的深入研究。本文在真实路网上测试了不同的图划分数量和边界点数量等因素对Arc-flags算法的影响,主要包括预处理时间和空间的消耗、在线查询时间和搜索范围等方面,并根据实验结果和分析提出了合理的图划分建议(如选用好的图划分方法减少边界点数量等),为改进和使用Arc-flags算法提供指导。
关键词: Arc-flags算法; 算法分析; 图划分; 最短路径; 预处理
刘惠民 , 孙广中 , 周英华 . 图划分对Arc-flags算法的影响[J]. 地球信息科学学报, 2016 , 18(11) : 1456 -1464 . DOI: 10.3724/SP.J.1047.2016.01456
The shortest path computation used in navigation system plays an important role in mobile Internet. Due to the increase of network scale and the moving terminal, the traditional serial algorithms for the calculation of the shortest path cannot meet the real-time requirements. The offline preprocessing technology is widely used in the shortest path computation. On the other hand, the increase of graph data scale will improve online query time for the shortest path query, so graph partition technology is used to partition road network graph data. The Arc-flags algorithm is a classic shortest path algorithm based on the preprocessing and graph partition technology, which provides efficient online shortest path query. Arc-flags have two main parts, one is graph partition and flags-setting algorithm and the other one is online query algorithm. Until now, existing research on Arc-flags algorithm mainly focus on the improvement of space and time-cost of preprocessing and comparison of the pros and cons of different network partitioning methods. However, the influence of the graph partitioning for Arc-flags algorithm is not analyzed in-depth. Our paper tested and analyzed the effect of different graph partitioning technology for Arc-flags algorithm in real road networks in many aspects, such as the pre-processing time, memory consumption and online query efficiency. The real road network data includes three public data sets: American New York City Road Network, American San Francisco Bay Area Road Network and American Northeast Road Network. In order to compare the effect of different graph partition technology, one graph partition tool Metis was used. We compared Arc-flags and simple Dijkstra algorithm. Arc-flags had much better performance on online query time. Also, we compared the results of Arc-flags based on different graph partition technology, the preprocessing time and the graph partition number was linear growth while the preprocessing time increased faster than the boundary point number. The graph partition number had little effect on online query time if the number arrived a large value. The searching range had little effect on online query time if the searching range reduced to a certain extent. If so, the main effect factor was memory access efficiency and so on, not the searching range. At last, we gave some reasonable graph partitioning suggestions according to our experimental results and analysis. We should use the best graph partitioning to partition road in order to reduce the boundary point number. Our research could provide some guidance to help the improve and use of the Arc-flags algorithm for shortest path algorithm in real navigation system.
Key words: Arc-flags; algorithm analysis; graph partitioning; shortest path; preprocessing
Tab. 1 Description of road network data sets表1 路网数据说明 |
数据名称 | 节点数 | 边数 |
---|---|---|
美国纽约路网NY | 264 346 | 733 846 |
旧金山湾区路网BAY | 321 270 | 800 172 |
美国东北路网NE | 15 24 453 | 3 897 336 |
Tab. 2 The shortest path calculation time of Naïve Dijkstra algorithm表2 朴素Dijkstra算法最短路径计算时间 |
数据名称 | 计算时间/ms |
---|---|
美国纽约路网NY | 27.89 |
旧金山湾区路网BAY | 32.78 |
美国东北路网NE | 192.12 |
Tab. 3 The shortest path searching range ofnaïve Dijkstra algorithm表3 朴素Dijkstra算法最短路径搜索范围 |
数据名称 | 搜索范围 |
---|---|
美国纽约路网NY | 314.89 |
旧金山湾区路网BAY | 333.34 |
美国东北路网NE | 649.12 |
Fig. 1 The boundary point number with differentnumber of graph-partitioning图1 不同图划分数量下边界点数量 |
Fig. 2 The preprocessing time with differentnumber of graph-partitioning图2 不同图划分数量预处理时间 |
Tab. 4 Space size with different number of graph-partitioning表4 不同图划分数量辅助空间需求大小 |
空间/MB | 划分数量 | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
200 | 400 | 600 | 800 | 1000 | 1200 | 1400 | 1600 | 1800 | 2000 | |
美国纽约路网NY | 17.50 | 34.99 | 52.49 | 69.99 | 87.48 | 104.98 | 122.47 | 139.97 | 157.47 | 174.96 |
旧金山湾区路网BAY | 19.08 | 38.16 | 57.23 | 76.31 | 95.39 | 114.47 | 133.54 | 152.62 | 171.70 | 190.78 |
美国东北路网NE | 92.93 | 185.85 | 278.78 | 371.71 | 464.63 | 557.56 | 650.49 | 743.42 | 836.34 | 929.27 |
Tab. 5 Algorithm query time with different number of graph-partitioning表5 不同图划分数量Arc-flags算法查询时间 |
时间/ms | 划分数量 | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
200 | 400 | 600 | 800 | 1000 | 1200 | 1400 | 1600 | 1800 | 2000 | |
美国纽约路网NY | 1.40 | 1.11 | 1.07 | 1.00 | 0.92 | 0.92 | 0.92 | 0.91 | 0.92 | 0.90 |
旧金山湾区路网BAY | 1.53 | 1.33 | 1.20 | 1.14 | 1.12 | 1.09 | 1.08 | 1.10 | 1.04 | 1.04 |
美国东北路网NE | 8.12 | 6.82 | 6.26 | 6.16 | 6.16 | 5.58 | 5.55 | 5.35 | 5.57 | 5.30 |
Fig. 3 Algorithm time acceleration with differentnumber of graph-partitioning图3 不同图划分数量下Arc-flags算法时间加速 |
Fig. 4 Ratio of query range before and after using Arc-flags with different number of graph-partitioning图4 不同图划分数量Arc-flags使用前后搜索范围比值” |
Tab. 6 Arc-flags query range with different number of graph-partitioning表6 不同图划分数量Arc-flags算法搜索范围 |
数据 | 划分数量 | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
200 | 400 | 600 | 800 | 1000 | 1200 | 1400 | 1600 | 1800 | 2000 | |
美国纽约路网 | 9.45 | 6 | 5.29 | 4.28 | 3.51 | 3.4 | 3.25 | 2.87 | 2.84 | 2.69 |
旧金山湾区路网 | 7.77 | 5.49 | 4.15 | 3.37 | 3.05 | 2.91 | 2.51 | 2.38 | 2.29 | 2.21 |
美国东北路网 | 16.46 | 10.84 | 8.22 | 7.03 | 6.43 | 5.49 | 4.96 | 4.28 | 4.31 | 4.14 |
The authors have declared that no competing interests exist.
[1] |
|
[2] |
|
[3] |
|
[4] |
|
[5] |
|
[6] |
|
[7] |
|
[8] |
|
[9] |
|
[10] |
|
[11] |
|
[12] |
|
[13] |
|
[14] |
|
[15] |
|
[16] |
|
[17] |
|
[18] |
|
/
〈 |
|
〉 |